|
Friday, March 14, 2008 |
|
|
|
|
Chromatic Zeros of Graphs |
|
|
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. |