On Friday, I gave a talk (chromaticpolynomials) to the “Junior Mathematics Seminar” in our department; this is a seminar attended and organized by the students, with staff only allowed as speakers.

I chose to speak about one of my favourite topics, namely the chromatic roots of graphs, for three reasons: firstly, it is a very accessible topic for undergraduates, secondly, I have spoken about it frequently and so have many diagrams and plots already prepared, and thirdly, because Alan Sokal and I (along with other collaborators) are having another push at trying to make some progress with some of the outstanding conjectures.

One of the questions is how to tighten the bounds on chromatic roots as a function of the maximum degree $\Delta(G)$ of a graph $G$. It had long been conjectured, by Norman Biggs and his collaborators, that chromatic roots of graphs should be bounded by some function $f(\Delta(G))$ of the maximum degree. This was eventually proved by Alan (http://arxiv.org/abs/cond-mat/9904146) but the bound he proved — that chromatic roots have modulus no more than about $8\Delta(G)$ — is almost certainly nowhere near tight.

I have a very strong conjecture on which I have made no progress in 20 years — my early computations on chromatic roots made me believe the following.

Conjecture: The chromatic root of largest modulus among all $r$-regular graphs is a chromatic root of the complete bipartite graph $K_{r,r}$ (with the sole exception of the complete graph $K_4$ for $r=3$.

(Unpublished work by Sokal and Jesus Salas show that this would give a bound of approximately $1.6\Delta(G)$.)

In other words, I believe that the largest chromatic root belongs to one of the smallest possible graphs!  Despite many years of attempting to disprove this,  and millions of chromatic polynomials computed and their roots extracted, I’ve never managed to find a single counterexample.

There are many other attractive conjectures regarding the bounds on chromatic roots, but I’ll leave them for future posts.