Title: On the complexity of generalized chromatic polynomials,
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.