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

$q (q-1) (q-2)^2 (q^4 - 9q^3 + 37 q^2 - 76 q + 67)$

and

$q (q-1) (q-2)^2 (q^4 - 10q^3 + 45 q^2 - 99 q + 90)$

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 $G$ with no independent set of vertices $S$ such that the number of components of $G-S$ is greater than $|S|$ has no chromatic roots in the interval $(1,2)$. We coined the term $\alpha$-1-tough for this property, combining terminology from independent sets (the $\alpha$) 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 $(1,2)$, disproving a conjecture of Bill Jackson, but they also all turned out to not be $\alpha$-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 $G$ is 3-connected, non-bipartite and $\alpha$-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 $(1,2)$ – or perhaps it will rely on this conjecture! That’s the joy of research, I guess.

Given a graph and a group of automorphisms of it (which I will forebear to name here, since I like groups to be $G$), the orbital chromatic polynomial is the polynomial whose value at a positive integer $q$ is the number of orbits of the group on proper $q$-colourings of the graph.
For example, consider the graph obtained by deleting an edge from the complete graph on 4 vertices. Its chromatic polynomial is $q(q-1)(q-2)^2$. If the group is the cyclic group of order 2 generated by the transposition swapping the ends of the missing edge, then the orbital chromatic polynomial is $q(q-1)^2(q-2)/2$ (the division by 2 is just a normalisation).