The Complexity of Counting Generalized Colorings: New Results and Challenges

Let $P$ be a graph property. We look at graph colorings with $k$ colors where each color class induces a graph satisfying $P$. By a result of Makowsky and Zilber (2005) the number of such colorings  $\chi_P(G;k)$ is a polynomial in $k$. We present recent results and open problems on the complexity of evaluating $\chi_P(G;\lambda)$ for various  properties $P$ and (not only integer) values of $\lambda$. 

 

This is joint work with A. Goodall, M. Hermann, T. Kotek and S. Noble which was initiated during last year's program "Counting Complexity and Phase Transitions". See also arXiv:1701.06639v1 [math.CO].