Counting \(4 \times 4\) matrix partitions of graphs

DOI10.1016/j.dam.2016.05.001zbMath1344.05113arXiv1407.7799OpenAlexW1480571425WikidataQ56323759 ScholiaQ56323759MaRDI QIDQ313799

David Richerby, Martin Dyer, Leslie Ann Goldberg

Publication date: 12 September 2016

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1407.7799

zbMATH Keywords

complexity dichotomy\(\#\mathrm{P}\)-completenesscomplexity of countingmatrix partitions of graphs

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Towards a dichotomy theorem for the counting constraint satisfaction problem
• Complexity of graph partition problems
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• The Complexity of Enumeration and Reliability Problems
• List Partitions
• Counting Partitions of Graphs
• The complexity of the counting constraint satisfaction problem

This page was built for publication: Counting \(4 \times 4\) matrix partitions of graphs