Skip to content

Chromatic Roots I

September 12, 2011

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.

Advertisements
No comments yet

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: