On the complexity of generalized chromatic polynomials

DOI10.1016/J.AAM.2017.04.005MaRDI QIDQ679542zbMATH OpenOpenAlexFDO

Authors Steven D. Noble, Andrew Goodall, Miki Hermann, 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, https://eprints.bbk.ac.uk/id/eprint/18934/1/18934.pdf

zbMATH Keywords

chromatic polynomialcounting complexitygraph polynomials

Mathematics Subject Classification ID

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

Abstract: J. Makowsky and B. Zilber (2004) showed that many variations of graph colorings, called CP-colorings in the sequel, give rise to graph polynomials. This is true in particular for harmonious colorings, convex colorings, mcc_t-colorings, and rainbow colorings, and many more. N. Linial (1986) showed that the chromatic polynomial $chi(G;X)$ is #P-hard to evaluate for all but three values X=0,1,2, where evaluation is in P. This dichotomy includes evaluation at real or complex values, and has the further property that the set of points for which evaluation is in P is finite. We investigate how the complexity of evaluating univariate graph polynomials that arise from CP-colorings varies for different evaluation points. We show that for some CP-colorings (harmonious, convex) the complexity of evaluation follows a similar pattern to the chromatic polynomial. However, in other cases (proper edge colorings, mcc_t-colorings, H-free colorings) we could only obtain a dichotomy for evaluations at non-negative integer points. We also discuss some CP-colorings where we only have very partial results.

Recommendations

• Complexity of graph polynomials
• On Counting Generalized Colorings
• The complexity of computing the sign of the Tutte polynomial
• Foundations of the chromatic polynomial
• An extension of the bivariate chromatic polynomial

Cites work

• scientific article; zbMATH DE number 3611388 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1057876 (Why is no real title available?)
• scientific article; zbMATH DE number 1545676 (Why is no real title available?)
• A computational framework for the study of partition functions and graph polynomials
• Acyclic coloring of graphs
• Acyclic colorings of planar graphs
• Characterizations of derived graphs
• Complexity of generalized satisfiability counting problems
• Complexity of the Bollobás-Riordan polynomial. Exceptional points and uniform reductions
• Computational complexity of Holant problems
• Connection matrices and the definability of graph parameters
• Defective coloring revisited
• Efficient approximation of convex recolorings
• From a zoo to a zoology: Towards a general theory of graph polynomials
• Graph Classes: A Survey
• Graph homomorphisms with complex values: a dichotomy theorem
• Hard Enumeration Problems in Geometry and Combinatorics
• Hardness and algorithms for rainbow connection
• Harmonious colourings of graphs
• Holographic Algorithms
• On Counting Generalized Colorings
• On cocolourings and cochromatic numbers of graphs
• On counting generalized colorings
• On sequences of polynomials arising from graph invariants
• On the Complexity of General Graph Factor Problems
• On the Harmonious Coloring of Graphs
• On the Structure of Polynomial Time Reducibility
• On the injective chromatic number of graphs
• On the location of roots of graph polynomials
• Partitioning into graphs with only small components
• Rainbow connection in graphs
• Systems of distinct representatives and linear algebra
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• The Complexity of Enumeration and Reliability Problems
• The Complexity of Planar Counting Problems
• The complexity of \(G\)-free colourability
• The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems
• The complexity of generalized graph colorings
• The complexity of harmonious colouring for trees
• The complexity of partition functions
• The existence of uniquely \(-G\) colourable graphs
• Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard

Cited in

(5)

• Harary polynomials
• On sequences of polynomials arising from graph invariants
• On the algebraic complexity of some families of coloured Tutte polynomials
• Acyclic polynomials of graphs
• A logician's view of graph polynomials

This page was built for publication: On the complexity of generalized chromatic polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q679542)