Please use this identifier to cite or link to this item: http://bura.brunel.ac.uk/handle/2438/2760
Title: Counting cocircuits and convex two-colourings is #P-complete
Authors: Noble, S D
Keywords: Graph colouring;#P-complete;Convex colouring;Cocircuits
Issue Date: 2008
Publisher: Mathematics Preprint Archive
Abstract: We prove that the problem of counting the number of colourings of the vertices of a graph with at most two colours, such that the colour classes induce connected subgraphs is #P-complete. We also show that the closely related problem of counting the number of cocircuits of a graph is #P-complete.
URI: http://bura.brunel.ac.uk/handle/2438/2760
Appears in Collections:Mathematical Science
Computer Science
Dept of Mathematics Research Papers

Files in This Item:
File Description SizeFormat 
convexcolourings.pdf131.28 kBAdobe PDFView/Open


Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.