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.

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.