Talks
Spring 2016

The Complexity of Counting Generalized Colorings: New Results and Challenges

Thursday, Jun. 8, 2017 9:15 am10:15 am

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$.