The shameful conjecture

This is the story of the shameful conjecture, which started with Dominic Welsh, was almost solved by Paul Seymour, and eventually resolved by my friend Fengming Dong from Nanyang in Singapore.

The conjecture concerns a graph parameter called the mean colour number defined as follows: If $G$ is an $n$ -vertex graph, then $\mu(G)$ is the average number of colours used over all proper colourings of $G$ using a palette of n colours.

As this is a slightly strange parameter, an example is probably in order, and it seems only appropriate to use the Welsh graph (that is, the graph $K_4 \backslash e$ obtained by deleting one edge from $K_4$ ) for this purpose.

Using a palette of $4$ colours, there are $4! = 24$ colourings that use all four of the colours. There are $3! = 6$ colourings that use a fixed set of $3$ colours (the two vertices of degree two must be assigned the same colour), and there are $4$ ways of choosing $3$ colours of out $4$ , making a total of $24$ colourings using three colours. So the mean colour number of the Welsh graph is $7/2$ as the $48$ colourings are evenly divided between $3$ – and $4$ -colourings (there are no colourings with fewer than $3$ colours).

Using some straightforward identities, it can be shown that

$\displaystyle \mu(G) = n \times \left( 1 - \frac{P_G(n-1)}{P_G(n)} \right)$

where $P_G(x)$ is the chromatic polynomial of $G$ .

The chromatic polynomial of the Welsh graph is $x(x-1)(x-2)^2$ so for this graph the expression has the value $4 \times (1 - 6/48) = 7/2$ as expected.

It is obvious that the complete graph $K_n$ has the largest mean colour number, because every colouring requires $n$ colours, so $\mu(K_n) = n$ .

At the other extreme is the empty graph on $n$ vertices, which has chromatic polynomial $x^n$ and thus

$\displaystyle \mu(E_n)= n \times (1-(n-1)^n/n^n)$

and as $n$ gets large the factor $(n-1)^n/n^n$ famously converges to $1/e$ from below.

But hang on, why did I say “the other extreme”? How do I know that the empty graph $E_n$ has the lowest mean colour number? Of course, it seems intuitively obvious that adding an edge to a graph can only increase the average number of colours required to colour it. Unfortunately, while it is intuitively obvious, it is not actually true that adding edges increases the mean colour number. Mike Mosca (yes, the quantum crypto guy from Waterloo) found an infinite family of counterexamples, of which the smallest has only 6 vertices.

So is it even true that $E_n$ is the extreme graph? Bartels and Welsh conjectured that this is indeed the case – namely that for any $n$ -vertex graph $G$

$\displaystyle \frac{P_G(n)}{P_G(n-1)} \geq \frac{n^n}{(n-1)^n} > e$

For a graph theorist, it is a little embarrassing to define a parameter applicable to all graphs, with the complete graph trivially at one extreme, and then be unable to show that the empty graph is the other extreme. In fact, more than just embarrassing, perhaps even positively shameful.

Thus the shameful conjecture was christened.

Now Paul Seymour enters the ring. Normally if he turns his attention to some topic, even briefly, he quickly vacuums up and solves most of the known unsolved conjectures, generates some much harder and deeper conjectures, and then moves on. In this case though, he didn’t quite knock off the shameful conjecture. Instead, he proved that for any n-vertex graph $G$ ,

$\displaystyle \frac{P_G(n)}{P_G(n-1)} \geq \frac{685}{252} \approx 2.7182539 \ldots$

As $e \approx 2.7182818 \ldots$ , this value is just a little bit too low to prove the shameful conjecture.

The shameful conjecture hung on for another few years, but ultimately Fengming Dong (who has resolved quite a number of difficult chromatic and flow polynomial questions), used one of his typically intricate and ingenious proofs to show that the shameful conjecture is indeed true.

I don’t know if the shameful conjecture has stimulated any further research, or if the mean colour number has found any other uses, but I’ve always liked the story…