The Complexity of Counting Generalized Colorings: New Results and Challenges

Johann A. Makowsky

Faculty of Computer Science, Technion – Israel Institute of Technology, Haifa, Israel

Faculty of Computer Science, Technion – Israel Institute of Technology, Haifa, Israel

2017/07/14 Fri 4PM-5PM

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 ?

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.

_{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.

Tags: JohannMakowsky