Peter Cameron (School of Mathematical Sciences, Queen Mary, University of London, UK)
16/04/2012 Segunda-feira, 16 de Abril de 2012, 14:30-15:30, Sala B3-01 
Institute for Interdisciplinary Research - University of Lisbon
Talk 3: Algebraic properties of chromatic roots
The \emph{chromatic polynomial} of a graph is the polynomial whose value at a positive integer $q$ gives the number of proper $q$-colourings of the graph. The study of roots of chromatic polynomials has a long history. For example, the four-colour conjecture (now theorem) asserts that $4$ is not a root of the chromatic polynomial of a planar graph. More recently, physicists have been interested in this, because of connections with statistical mechanics (specifically, the partition function of the \emph{Potts model}). Alan Sokal proved the surprising result that chromatic roots are dense in the complex plane. However, little is known about their algebraic properties (such as splitting fields and Galois groups). A recent research project has attempted to address this. One of the main goals is the conjecture that, if $\alpha$ is any algebraic integer, there is a positive integer $n$ such that $\alpha+n$ is a chromatic root. This has been proved for quadratic and cubic integers. There are some speculations about how the chromatic polynomial of a random graph factorises.
© 2010 CAUL