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.

Lecture 1: A Landscape of Graph Polynomials.

We introduce the most prominent graph polynomials (characteristic, Laplacian, chromatic, matching, Tutte) and discuss how to compare them.

Lecture 2: Why is the Chromatic Polynomial a Polynomial?

We give an alternative proof for the fact that the chromatic polynomial is indeed a polynomial. From this we introduce generalized chromatic polynomials, and show that this actually represents the most general case; Every (reasonably defined) graph polynomial can be represented as a generalized chromatic polynomial.

Lecture 3: Hankel matrices and Graph Polynomials.

We introduce Hankel matrices of graph paramaters, which generalize Lovasz’ connection matrices. We show that many (but not all) graph polynomials have Hankel matrices of finite rank. We show how to use the Finite Rank Property to show definability/non-definability of graph parameters/polynomials in Monadic Second Order Logic.