KAIST Discrete Math Seminar

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 ?_P(G;k) is a polynomial in k. We present recent results and open problems on the complexity of evaluating ?_P(G;λ) for various properties P and (not only integer) values of λ.
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.