Counting cocircuits and convex two-colourings is #P-complete
classification
🧮 math.CO
cs.CC
keywords
countingp-completecocircuitsgraphnumberproblemclassesclosely
read the original 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.