ELC Seminar (C01 & Kawarabayashi ERATO)
Date: July 30
Time: 16:00 - 17:30
Place: CELC Seminar room (Rm.404)

Speaker: Johann Makowsky (Technion)

Title:
Why is the chromatic polynomial a polynomial?

Abstract 2: We give a proof different from Birkhoff's proof of
the fact that counting k-colorings of a graph gives rise to a
polynomial in k, the chromatic polynomial of the graph.  We use
this to show that many counting functions on graphs ared
 polynomials. We show that every univariate graph polynomial
definable in Second Order Logic is a generalized chromatic
polynomial. (Joint work with B. Zilber and T. Kotek)