Tutte seminar - Gordon Royle

Friday, March 14, 2008 3:30 pm - 4:30 pm EDT (GMT -04:00)

Chromatic Zeros of Graphs

Speaker: Gordon Royle
Affiliation: University of Western Australia
Room: Mathematics & Computer Building (MC) 5158


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.