Peter Cameron (School of Mathematical Sciences, Queen Mary, University of London, UK)
16/04/2012 Segundafeira, 16 de Abril de 2012, 14:3015:30, Sala B301
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 fourcolour 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.
http://caul.cii.fc.ul.pt/slides/PeterCameron_talk3.pdf/ 
