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

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
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.
URI: http://bura.brunel.ac.uk/handle/2438/2760
Appears in Collections:School of Information Systems, Computing and Mathematics Research Papers
Mathematical Science
Computer Science

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.

 


Library (c) Brunel University.    Powered By: DSpace
Send us your
Feedback. Last Updated: September 14, 2010.
Managed by:
Hassan Bhuiyan