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