On the complexity of generalized chromatic polynomials

作者：Goodall A; Hermann M; Kotek T; Makowsky J A^*; Noble S D

来源：Advances in Applied Mathematics, 2018, 94: 71-102.

DOI：10.1016/j.aam.2017.04.005

• Graph polynomials
• Counting complexity
• Chromatic polynomial

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.

• 出版日期2018-3