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;#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.
Appears in Collections:Computer Science
Dept of Mathematics Research Papers
Mathematical Sciences

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.