Skip to content

Chromatic Roots – the multiplicity of 2?

January 6, 2012

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.

About these ads
One Comment leave one →
  1. January 7, 2012 12:52 am

    This may be a complete red herring; but when I was looking at orbital chromatic polynomials, I found a somewhat similar phenomenon.

    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.

    Now the orbital chromatic polynomial has the same positive integer roots as the chromatic polynomial of the same graph (forgetting the group), since of course if there are no colourings then there are no orbits on colourings. But the multiplicities can change.

    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).

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

Follow

Get every new post delivered to your Inbox.

Join 41 other followers

%d bloggers like this: