Centenary of the Chromatic Polynomial

Regular readers of this blog (hi mum!) will already know that chromatic polynomials are one of my favourite research topics, and one on which I have made several posts.

Well, when I was in Sydney last year, my old friend Graham Farr pointed out that the cusp of 2012/2013 is the centenary of the chromatic polynomial, because the paper in which it originated “A determinant formula for the number of ways of coloring a map” was published in the Annals of Mathematics, 14 and dated 1912-1913. Of course the original aim was to prove the four-colour theorem quantitatively by showing that P(G,4) > 0 for any planar graph G, but this never worked out.

So it’s now been 100 years since the chromatic polynomial arrived, and there’s still lots about it that we don’t understand, so Happy Birthday, Chromatic Polynomial!

One of the most irritating things that we don’t understand is actually the very first conjecture about chromatic roots. In 1946, Birkhoff & Lewis did manage to prove that P(G,x) > 0 for a planar graph G and any real x \geq 5 and started the study of real chromatic roots. They also conjectured that P(G,x) > 0 for any real x \geq 4 which of course implies the four-colour theorem and more. While chromatic roots (integer, real, complex) have been intensively studied, partly because the chromatic polynomial is intimately related to the partition function of the q-state Potts model, it is slightly embarrassing that we cannot even answer this very first problem, now obviously known as the Birkhoff-Lewis conjecture.

Birkhoff-Lewis conjecture: If G is a planar graph then P(G,x) > 0 for x \in (4,5).

I’ve tried quite hard to solve this problem, but there are no obvious weak points to attack. Beraha and Kahane showed that planar graphs have complex chromatic roots arbitrarily close to 4, while Sokal showed that they have complex chromatic roots arbitrarily close to any point in the complex plane and I showed that they have real chromatic roots arbitrarily close to, but smaller than, 4.

So it’s just this one little interval (4,5) that is the only possibly unresolved root-free region amidst a sea of chromatic roots! I’m busy applying for grants now and working up to another attack on chromatic roots. I won’t promise to solve this problem of course, because it’s obviously hard, but I can always hope!

AustMS talk on chromatic roots

I gave my talk at the AustMS 2009 meeting yesterday, and have now uploaded the PDF slides of my talk which was called Chromatic Roots and Maxmaxflow.

I was lucky enough to be the “keynote” speaker at the special session on Combinatorics so I got a one-hour time slot, which is usually easier to deal with than a shorter one.

The talk itself was a more focussed variant of a talk I gave at the British Combinatorial Conference in July this year, and describes my recent work with Alan Sokal, which is essentially complete, but just needs wrestling into final publishable shape. Working with Alan is a tremendous privilege, but exploring every possible generalization, hypothsis-weakening and related application that his incredibly fertile brainĀ  throws up is incredibly time-consuming for a mere mortal!

Anyway the gist of this work is that we want to find a parameter to replace maximum degree in the result that the moduli of chromatic roots are bounded by a function of maximum degree. The parameter maxmaxflow which is defined to be the maximum number of edge disjoint paths between any pair of vertices is a promising alternative, and this talk gives a very general overview of our proof that it works for series-parallel graphs.

Blog at WordPress.com.

Up ↑