Counting the colourings

The four-colour theorem answers a question with a yes. A more informative question is how many proper colourings a graph has with $k$ colours available, and the answer to that is not a number but a function of $k$ — and the function is always a polynomial.

For the graph above the count is $k(k-1)(k-2)^2$: zero at $k = 0, 1, 2$, six at $k = 3$, thirty-six at $k=4$. The chromatic number — the least number of colours that works — is where the polynomial stops being zero, so the yes-or-no question is answered by a root.

The recursion that produces it #

Pick any edge $e$ of a graph $G$. Every colouring of $G$ with $e$ deleted falls into exactly two kinds: those giving the two ends of $e$ different colours, which are the proper colourings of $G$ itself, and those giving them the same colour, which are exactly the proper colourings of the graph with the two ends merged into one vertex. So

$$P_G(k) = P_{G-e}(k) - P_{G/e}(k),$$

where $G - e$ is the deletion and $G/e$ the contraction. Each of those has one fewer edge or one fewer vertex than $G$, so the recursion terminates — at a graph with no edges at all, whose colourings number $k^{V}$ because every vertex is free.

That termination is where the polynomiality comes from. Every leaf of the recursion contributes $\pm k^{m}$ for some $m$, so the total is a sum of powers of $k$ with integer coefficients. The counts are values of a polynomial because the recursion bottoms out at powers, and nothing else is needed to see it.

The figure’s table is computed the slow way — every one of the $k^V$ assignments is generated and checked — precisely so that the identity above is verified against brute force rather than assumed. A recursion that is believed rather than checked is how a wrong count becomes a printed number.

What the polynomial knows #

The polynomial carries more than the chromatic number, and the extras are not what anyone was looking for.

Its degree is the number of vertices, and its leading coefficient is $1$. With many colours available, almost every assignment is proper, so the count approaches $k^V$.

The next coefficient is minus the number of edges. $P_G(k) = k^V - E k^{V-1} + \cdots$, always. So the polynomial announces the size of the graph in its first two terms.

The coefficients alternate in sign, which is a theorem of Whitney’s, and their magnitudes count something concrete: the number of subsets of edges that form a spanning subgraph with a given number of connected components, weighted by whether the subset has an even or odd number of edges. A statement about counting colourings has turned into a statement about counting subgraphs, and the alternation is an inclusion–exclusion in disguise.

The multiplicity of zero as a root is the number of connected pieces. A graph in two pieces has $P_G(k) = P_1(k)P_2(k)$, and each factor has a root at zero.

Two families where the answer is a formula #

Some graphs give their polynomial up immediately, and the two easiest cases bracket everything else.

A tree on $V$ vertices has $P(k) = k(k-1)^{V-1}$, whatever its shape. Rooting it anywhere and colouring outward, each vertex after the first has exactly one coloured neighbour to avoid, so the choices multiply. That is why trees are two-colourable and why they are the easy case of nearly every graph question.

At the other end, the complete graph $K_V$ has $P(k) = k(k-1)(k-2)\cdots(k-V+1)$, the falling factorial: every vertex must differ from every other, so each in turn has one fewer choice. It is zero until $k$ reaches $V$, which is the statement that $V$ mutually adjacent regions need $V$ colours.

The complete graph is also the reason the five-colour and four-colour theorems say anything at all. $K_5$ needs five colours, so a graph containing it needs five — and the only reason no planar map ever needs five is that $K_5$ cannot be drawn in the plane without a crossing. The colouring theorems are statements about which complete graphs can be embedded, wearing different clothes.

Every other graph sits between those two, in a precise sense: for each $k$, the tree’s count is the largest and the complete graph’s the smallest among connected graphs on the same number of vertices. Adding an edge can only remove colourings, and the polynomial’s coefficients record exactly how many.

What the polynomial does not know #

The sixteen trees above raise the obvious question, and the answer is no: the polynomial does not determine the graph.

All sixteen are different graphs — different edge sets on the same four labelled points — and every one has the same polynomial. Any two trees on the same number of vertices are indistinguishable to it, and so are many pairs that are not trees.

That is worth stating plainly because a complete invariant would be an enormous thing to have, and this is not one. What the polynomial captures is a particular kind of information — vertex count, edge count, component count, and a weighted census of spanning subgraphs — and what it discards is how the edges are arranged, beyond those counts.

The stronger invariant in the same family is the Tutte polynomial in two variables, and it does not determine the graph either. Whether any reasonable invariant does is the graph isomorphism problem, and the current state of it is that nobody knows a polynomial-time test and nobody has proved there is none.

The values nobody asked for #

Here is the part that has no business being true.

Evaluate the chromatic polynomial at $k = -1$. For a graph on $V$ vertices, $(-1)^V P_G(-1)$ counts the acyclic orientations of the graph — the ways of putting an arrow on every edge so that no directed cycle results.

That is Stanley’s theorem, from 1973, and it is worth pausing on how strange it is. Colourings with a negative number of colours are meaningless. The polynomial that counts colourings, evaluated where its input has no interpretation, counts something else entirely — an object with no colours in it anywhere.

For the triangle, $P(k) = k(k-1)(k-2)$, so $(-1)^3 P(-1) = -(-1)(-2)(-3) = 6$: the six acyclic orientations of a triangle, which are the $2^3 = 8$ orientations minus the two cyclic ones. The arithmetic checks and the reason it checks is a genuine theorem rather than a coincidence.

This is a recurring phenomenon and it has a name: combinatorial reciprocity. A counting function is fitted by a polynomial on the values where it makes sense, and the polynomial’s values elsewhere count a related family. The same thing happens with lattice points in a dilated polygon, where the counting polynomial at negative arguments counts the interior points instead of all of them.

The moral is about what a formula is. Once a count has been extended to a polynomial, the polynomial is an object with its own life, and asking it questions the original count could not answer is not nonsense — it is a way of finding out what the original count was secretly about.

Who invented it, and what for #

George Birkhoff introduced the chromatic polynomial in 1912 for one purpose: to attack the four-colour conjecture.

The idea was that if the polynomial of every planar graph could be shown to be positive at $4$, the conjecture would follow — and a polynomial is a more tractable object than a case analysis, with tools available from algebra that a combinatorial argument cannot use. Birkhoff and, later, Lewis’s work on the roots was a serious programme along those lines.

It did not work. Nobody has ever proved $P_G(4) > 0$ for planar $G$ by studying the polynomial, and the four-colour theorem was eventually settled by exactly the case analysis the polynomial was invented to avoid. What Birkhoff’s tool did instead was become useful for other things — Whitney’s interpretation of the coefficients, Tutte’s two-variable generalisation, and, decades later, the Potts model of statistical mechanics, where the same polynomial is a partition function and its roots are phase transitions.

That is a common enough shape to be worth naming. A tool built to solve one problem fails at it, survives because it turns out to describe something else, and is remembered for the second thing. The chromatic polynomial is a poor route to four colours and an excellent object in its own right, and both halves of that sentence took decades to establish.

What it costs #

Computing the chromatic polynomial is expensive, and the recursion above is the reason.

Each step branches in two, and neither branch is much smaller than what it came from — one loses an edge, the other loses a vertex and usually several edges. The recursion tree has size exponential in the number of edges, and no substantially better method is known: computing the chromatic polynomial is $\#\mathrm{P}$-hard, which is the counting analogue of NP-hardness and, as usual, at least as bad.

Even deciding whether $P_G(3) > 0$ — three-colourability — is NP-complete, and it is worth noticing that this sits right next to a case that is trivial. Two-colourability is a five-line check: a graph is two-colourable exactly when it has no odd cycle, which a single traversal settles. Three is intractable. The jump between them is one of the sharpest thresholds in the subject, and it has no visible cause.

Against that, the polynomial for a planar graph is not easier in any known way, and the four-colour theorem’s content — that $P_G(4) > 0$ for every planar $G$ — remains a theorem about a quantity nobody can compute for a large graph.

Where it needs a condition #

The polynomial counts colourings of labelled vertices, and each colouring is counted once per labelling.

That means it over-counts in the sense a person usually means. The triangle has six three-colourings by this count, and only one if the colours are treated as interchangeable — the six are the same partition of the vertices with the three colour names permuted. Dividing by $k!$ works only when all $k$ colours are actually used, so the honest relation is a sum over the number of colours used, with Stirling numbers as the coefficients.

The counting also assumes the colours are distinguishable and unlimited in supply, which is what makes the answer a function of one number. Colouring with a limited palette — three reds and two blues — is a different question with no polynomial behind it, and it is harder.

Reading a root as a threshold #

One more habit the polynomial makes available, and it is the reason physicists care.

The chromatic number is a root, and a root is a place where a continuously varying quantity crosses zero. That converts a discrete question — is three enough? — into a question about where a curve meets an axis, and questions of the second kind are open to tools the first kind is not.

For a single small graph that is a curiosity. For a family of graphs growing without bound — a lattice of $n$ by $n$ points, say — the roots move, and where they accumulate as $n$ grows is a genuine question with physical content. In the Potts model the colours are spins, the polynomial is a partition function, and the accumulation points of its roots are the temperatures at which the material’s behaviour changes abruptly. A phase transition is a limit of roots.

That is a long way from maps, and the route is short: count instead of decide, notice the count is a polynomial, and then ask where the polynomial vanishes. Each step is small and the destination is in a different subject.

Where the roots can be, and where they cannot #

Reading the chromatic number as a root invites the question of where the other roots sit, and the answer is one of the more surprising pieces of structure in the subject: large stretches of the number line are forbidden to them entirely.

No chromatic polynomial has a negative root, and none has a root strictly between zero and one. Those follow from the alternating signs of the coefficients and from a short argument about the count being positive on the unit interval. So the roots start at one, where every graph with an edge vanishes, and continue upward.

And then there is a gap. Jackson proved in 1993 that no chromatic polynomial of any graph whatever has a root in the interval from one up to $32/27$ — a little under $1.19$. That is a strange constant to find guarding a strange gap, and the bound is sharp: roots accumulate at its upper end.

Above it, everything is possible. Thomassen showed in 1997 that chromatic roots are dense in the whole ray from $32/27$ upward — for any real number past that threshold and any tolerance, some graph has a chromatic root within it. So the picture on the real line is complete: a forbidden region, one isolated point at one, a small forbidden interval, and then roots everywhere.

Planar graphs have their own forbidden interval, and it is the four-colour theorem’s neighbourhood. Birkhoff and Lewis proved in 1946 that no planar graph has a chromatic root in the interval from four up to five. That result is stronger than half of the four-colour theorem where it applies and does not imply it: it says the polynomial does not vanish just above four, and says nothing about four itself. Birkhoff’s programme was to close the last step by pushing the interval down to include its endpoint, and it never closed.

There is one more constant in this landscape and it belongs to a different anchor. Tutte discovered in 1970 that the golden ratio squared — a little over $2.6$ — is special for planar triangulations: the chromatic polynomial evaluated there is never zero, and its size is bounded by a power of the golden ratio that shrinks as the graph grows. So a triangulation of a hundred vertices has a chromatic polynomial whose value at that point is astronomically small and provably not nothing.

That was taken at the time as evidence for four-colourability, and it is a fair example of what evidence looks like in this subject: not a partial colouring, not a checked family of maps, but a number that ought to be able to vanish and does not, at a point nobody had any reason to look at. The golden ratio is not in the problem anywhere — there are no pentagons, no continued fractions, no self-similar rectangles — and it turns up as the one place a planar triangulation’s colouring count can be controlled exactly.

What the picture cannot show #

The tables in these figures stop at five colours because the counts are made by brute force and the work grows like $k^V$. The polynomial they determine is exact and infinite in reach; the evidence for it drawn here is six values.

Six values do determine a polynomial of degree four uniquely, so nothing is being hidden — but the reason the counts lie on a polynomial at all is the recursion, not the table, and a reader looking only at the numbers would be entitled to ask why some other function does not fit them equally well. It does not, and the argument for that is in the prose.

Nor can any figure show the acyclic orientations claim. It relates two counts, one of which is evaluated at an input the picture cannot have — there is no drawing of a graph coloured with minus one colours, and the theorem’s content is that the polynomial does not care.

The ladder from here #

Below: the four-colour theorem, and the five-colour proof that can be read. Above and sideways: the map on a torus, where the counting bound is attained; the Tutte polynomial, of which this is a one-variable specialisation and which counts spanning trees, forests and flows by the same deletion–contraction recursion; and the Potts model of statistical physics, whose partition function is the chromatic polynomial with the colours read as spins.

That last connection is the reason a great deal of work has gone into the roots of these polynomials. The physical question — where does a magnet’s behaviour change abruptly — becomes the mathematical question of where the roots of a chromatic polynomial accumulate as the graph grows, and the answers are still incomplete.

From deciding to counting #

The lasting point is what changed when the question did.

Can this graph be four-coloured is a decision. It has two possible answers, it hides all its structure in a yes, and the proof that settled it for planar graphs is a case analysis no person can hold. How many ways is a count, its answer is a polynomial, and the polynomial contains the decision as the location of a root along with the edge count, the component count, an inclusion–exclusion over subgraphs, and a second combinatorial family living at the negative integers.

Replacing a yes-or-no question by a counting question is one of the standard upgrades in combinatorics, and it usually pays the same way. The number of ways to cut a polygon is more informative than knowing it can be cut; the number of derangements is more informative than knowing one exists. The count carries structure that the decision throws away, and the structure is where the connections to everything else turn out to be.