Counting List Matrix Partitions of Graphs

DOI10.1137/140963029zbMath1329.68139arXiv1306.5176OpenAlexW1940012286MaRDI QIDQ2944567

Leslie Ann Goldberg, Andreas Göbel, David Richerby, Colin McQuillan, Tomoyuki Yamakami

Publication date: 2 September 2015

Published in: SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

graph algorithmscomplexity dichotomymatrix partitions of graphscounting problems\#P-completeness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Enumeration in graph theory (05C30) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Unnamed Item
• An algorithm for finding homogeneous pairs
• The strong perfect graph theorem
• Towards a dichotomy theorem for the counting constraint satisfaction problem
• Bull-free Berge graphs are perfect
• List homomorphisms to reflexive graphs
• Algorithmic graph theory and perfect graphs
• Partitions of graphs into one or two independent sets and cliques
• List homomorphisms and circular arc graphs
• Normal hypergraphs and the perfect graph conjecture
• An Effective Dichotomy for the Counting Constraint Satisfaction Problem
• The Complexity of the Counting Constraint Satisfaction Problem
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• List Partitions
• Bi‐arc graphs and the complexity of list homomorphisms
• Counting Partitions of Graphs
• Full Constraint Satisfaction Problems
• The structure of hereditary properties and colourings of random graphs

This page was built for publication: Counting List Matrix Partitions of Graphs