Brunel University Research Archive (BURA) >
Research Areas >
Computer Science >

Please use this identifier to cite or link to this item:

Title: Counting cocircuits and convex two-colourings is #P-complete
Authors: Noble, S D
Keywords: Graph colouring
Convex colouring
Publication 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.
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.