My favourite problems in the theory of chromatic roots have a tendency to crop up frequently and I often find myself frantically searching through old emails or (worse) trying to dig up old notes.
One of these problems is the following question:
Is there a combinatorial interpretation for the multiplicity of 2 as a root of the chromatic polynomial of a graph?
(For general background, see my previous post on chromatic roots and the accompanying PDF.)
The specific background to this question is that there are well-understood combinatorial interpretations for the multiplicity of 0 as a chromatic root — it is simply the number of connected components of the graph. If a graph is connected (and hence 0 is a simple chromatic root), then the multiplicity of 1 as a chromatic root is the number of blocks (maximal 2-connected components) of the graph. So we would like a statement that says “if a graph is 2-connected (and so both 0 and 1 are simple chromatic roots) then the multiplicity of 2 as a chromatic root is the number of ….”. Unfortunately it all grinds to a halt here because, to my knowledge, nobody knows how to complete that sentence.
Well, can we at least say something about 3-connected graphs? If the pattern continues, then even if the unknown sentence were fiendishly complicated, it would presumably have the corollary that “if a graph is 3-connected then it has 0, 1 and 2 as simple chromatic roots”. Unfortunately this is just not true. Firstly, there are bipartite graphs for which 2 is not a chromatic root at all, but I will temporarily ignore those. Secondly, there are honest-to-goodness 3-connected non-bipartite graphs for which 2 is a multiple chromatic root.
Here are the 2 smallest such graphs:
The two graphs have chromatic polynomials
and so obviously have 2 as a chromatic root of multiplicity 2.
So, what makes these graphs special? Or is it just an accident? I don’t know, but I strongly suspect that it is the 3 red vertices that are to blame — they form an independent set of three vertices whose deletion leaves four components. Fengming Dong conjectured that a 3-connected graph with no independent set of vertices such that the number of components of is greater than has no chromatic roots in the interval . We coined the term -1-tough for this property, combining terminology from independent sets (the ) and from the study of toughness in graphs (the 1-tough part). Subsequently I found some 3-connected graphs that did have chromatic roots in , disproving a conjecture of Bill Jackson, but they also all turned out to not be -1-tough.
Both Fengming and I have tried hard, separately, and together to prove this conjecture, but it remains resolutely unproved. But perhaps a first step would be just to focus on the multiplicity of 2, and so I will conclude with a perhaps more modest conjecture:
If is 3-connected, non-bipartite and -1-tough, then 2 is a simple root of its chromatic polynomial.
Maybe this could be easier than the conjecture about roots in the interval – or perhaps it will rely on this conjecture! That’s the joy of research, I guess.