Tutte seminar - Gordon Royle

Chromatic Zeros of Graphs

Abstract:

The chromatic polynomial P(G,k) of a graph G is the polynomial that counts the number of proper k-colourings of the graph. It was introduced in 1912 by Birkhoff in an attempt to find an analytic proof that P(G,4) > 0 whenever G is planar --- in other words, to prove the 4-colour theorem. Although not successful, this work initiated the study of the real and complex zeros of the chromatic polynomial, a subject that has gained considerable momentum over the last few years, particularly due to its interactions with statistical physics.
In this talk I will survey the current "state of the art" in this area, present some recent results of my own and discuss various open problems.