Brunel University Research Archive(BURA) preserves and enables easy and open access to all
types of digital content. It showcases Brunel's research outputs.
Research contained within BURA is open access, although some publications may be subject
to publisher imposed embargoes. All awarded PhD theses are also archived on BURA.
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: | Computer Science Dept of Mathematics Research Papers Mathematical Sciences |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| convexcolourings.pdf | 131.28 kB | Adobe PDF | View/Open |
Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.