On the complexity of generalized chromatic polynomials

DOI10.1016/j.aam.2017.04.005zbMath1378.05059arXiv1701.06639OpenAlexW2580993430MaRDI QIDQ679542

Steven D. Noble, Miki Hermann, Andrew J. Goodall, Tomer Kotek, Johann A. Makowsky

Publication date: 11 January 2018

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

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

zbMATH Keywords

chromatic polynomialcounting complexitygraph polynomials

Mathematics Subject Classification ID

Graph polynomials (05C31) Nonnumerical algorithms (68W05) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Harary polynomials, On sequences of polynomials arising from graph invariants, Acyclic polynomials of graphs, A logician's view of graph polynomials

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems
• Hardness and algorithms for rainbow connection
• Harmonious colourings of graphs
• On the location of roots of graph polynomials
• Complexity of the Bollobás-Riordan polynomial. Exceptional points and uniform reductions
• From a zoo to a zoology: Towards a general theory of graph polynomials
• On cocolourings and cochromatic numbers of graphs
• The complexity of harmonious colouring for trees
• The complexity of \(G\)-free colourability
• The existence of uniquely \(-G\) colourable graphs
• Partitioning into graphs with only small components
• On the injective chromatic number of graphs
• Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard
• Complexity of generalized satisfiability counting problems
• The complexity of generalized graph colorings
• On sequences of polynomials arising from graph invariants
• The complexity of partition functions
• Efficient approximation of convex recolorings
• Connection Matrices and the Definability of Graph Parameters
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• On the Complexity of General Graph Factor Problems
• Computational Complexity of Holant Problems
• Defective coloring revisited
• On the Harmonious Coloring of Graphs
• Rainbow connection in graphs
• Graph coloring with no large monochromatic components
• Holographic Algorithms
• On Counting Generalized Colorings
• Hard Enumeration Problems in Geometry and Combinatorics
• The Complexity of Enumeration and Reliability Problems
• Acyclic coloring of graphs
• On the Structure of Polynomial Time Reducibility
• The Complexity of Planar Counting Problems
• Graph Classes: A Survey
• Systems of distinct representatives and linear algebra
• Characterizations of derived graphs
• A Computational Framework for the Study of Partition Functions and Graph Polynomials
• Graph Homomorphisms with Complex Values: A Dichotomy Theorem
• Acyclic colorings of planar graphs