One colour more than the busiest point

The colourings on this shelf so far have coloured points: five colours for any map, four with a computer’s help, and the order a greedy rule visits the points. Colouring the edges instead turns out to be a different subject with a much tidier answer. Give each edge a colour so that edges meeting at a point have different colours, and ask how few colours suffice. The answer is either the largest number of edges at any point, or one more — never anything else.

That theorem, proved by Vadim Vizing in 1964, splits every graph into two classes. The first needs only as many colours as its busiest point has edges, the second needs one more, and the frustrating part is that telling them apart is hard: deciding whether a graph with three edges at every point needs three colours or four is as hard as any problem in its family. And yet almost every graph is in the first class, and the graphs in the second all seem to contain the same kind of obstacle.

The lower bound and the gap #

Call the largest number of edges at any point $\Delta$. A point with $\Delta$ edges needs $\Delta$ different colours on them, so at least $\Delta$ colours are needed overall. The least number that suffices is the chromatic index. For the Petersen graph, every point has three edges, and three colours would mean splitting the fifteen edges into three groups of five, each group touching every point exactly once: three perfect matchings. An exhaustive search, which tries every colouring of the edges in turn and backs up the moment two edges at a point clash, finds that no such split exists. Four colours are needed, and the hero shows four suffice.

The surprise is that the gap never exceeds one. A greedy argument gives $2\Delta - 1$: colour the edges one by one, and each new edge clashes with at most $\Delta - 1$ edges at each end. Vizing’s theorem says $\Delta + 1$ always suffices, for every graph whatever its shape. His proof is a recolouring argument of the kind used for the five colour theorem: when an edge cannot be coloured, look at a “fan” of edges around one of its ends and a chain of edges alternating between two colours, and swap the colours along the chain to free a colour for the edge. Every swap keeps the colouring proper, and the argument shows a free colour can always be made.

The recolouring, followed through #

The proof is worth following once, because it is constructive and it shows where the extra colour is used. Suppose every edge but one, from $u$ to $v$, has been coloured with $\Delta + 1$ colours. Each point has at most $\Delta$ edges, so at every point at least one colour is missing. If some colour is missing at both $u$ and $v$, use it and stop.

Otherwise, let $a$ be a colour missing at $u$ and $b$ a colour missing at $v$. Follow the path that starts at $u$ and alternates between edges coloured $b$ and edges coloured $a$. Such a path cannot branch, since each point has at most one edge of each colour, so it is a simple chain that ends somewhere. Swapping $a$ and $b$ along it keeps the colouring proper, and it frees $b$ at $u$ — unless the chain runs into $v$, which is the case that needs care. Vizing’s idea is to consider not one edge at $u$ but a fan of them, $uv_1, uv_2, \ldots$, each $v_{i+1}$ chosen so that the colour of $uv_{i+1}$ is missing at $v_i$, and to rotate colours along the fan so that the uncoloured edge moves to a place where the chain cannot interfere. The argument always succeeds with one spare colour, and it gives an algorithm that colours any graph with $\Delta + 1$ colours in time polynomial in its size. Jayadev Misra and David Gries gave a clean version of it in 1992.

What the argument cannot do is decide whether the spare colour was needed. It colours the Petersen graph and a prism equally happily with four colours, and nothing in it notices that the prism could have managed with three.

Shannon’s bound, when edges can repeat #

If two points may be joined by several edges — as when wires between the same two terminals each need a different colour code — the theorem changes. Claude Shannon, studying exactly that problem in 1949, the year after his theory of noisy channels, proved that $\lfloor 3\Delta/2 \rfloor$ colours always suffice for such multigraphs, and that this can be needed: three points joined in a triangle by $\Delta/2$ edges on each side have $3\Delta/2$ edges that all pairwise meet. Vizing’s theorem extends with the multiplicity added: $\Delta$ plus the largest number of edges joining any two points is enough. For ordinary graphs, with no repeated edges, both bounds come down to $\Delta + 1$.

A round robin is an edge colouring #

The simplest graphs where the question is interesting are the complete ones, where every two points are joined. They are also the oldest application.

Read each point as a player, each edge as a match and each colour as a round in which nobody plays twice. A round-robin tournament schedule is exactly an edge colouring of the complete graph. With 8 players the busiest point has 7 edges, and 7 rounds suffice. The classical construction puts one player in the centre and seven round a circle; in round $r$ the centre plays circle player $r$, and the others pair off along chords at right angles to that line. The figure checks that edges of one colour never meet.

With 7 players each point has 6 edges, but 6 rounds are not enough. In each round at most three matches can be played, since seven players cannot all be paired, so 21 matches take at least 7 rounds. The complete graph on an odd number of points is the simplest member of the second class, and the reason is a counting argument: there are too many edges for $\Delta$ colours to cover, because each colour can cover at most $\lfloor n/2 \rfloor$ edges.

Two sides, and the degree is enough #

For graphs whose points split into two sides, with every edge going across, $\Delta$ colours always suffice. Dénes König proved this in 1916, and the proof is Hall’s theorem used repeatedly. A bipartite graph has a matching that touches every point of largest degree. Give that matching one colour and remove it; what is left is bipartite with largest degree $\Delta - 1$, and induction finishes the job. For a regular bipartite graph each colour class is a perfect matching, which is why such graphs have so many perfect matchings.

There is a pleasing special case. Colour the edges of the complete bipartite graph with $n$ points a side using $n$ colours, and write the colour of the edge from row $i$ to column $j$ in cell $(i, j)$ of a table. Each row and each column contains every colour exactly once: the table is a Latin square. Edge colourings of complete bipartite graphs are exactly Latin squares, and counting them is counting colourings.

Every graph on up to six points #

The theorem says every graph needs $\Delta$ or $\Delta + 1$ colours. Which do the small graphs need?

There are 1, 2, 4, 11, 34 and 156 graphs on 1 to 6 points up to relabelling, found here by listing every set of edges and keeping the one with the smallest code over all relabellings. The search puts most of them in the first class. On six points, 145 of the 156 need only $\Delta$ colours and 11 need one more; on five points 6 of 34 need one more. The first member of the second class is the triangle, with $\Delta = 2$ and three edges that all meet.

The obstruction is always of the same kind. A set of $k$ points spanning more than $\Delta \lfloor k/2 \rfloor$ edges is overfull: each colour covers at most $\lfloor k/2 \rfloor$ of those edges, so $\Delta$ colours cannot cover them all. A triangle with $\Delta = 2$ has three edges against a capacity of two. The complete graph on five points has ten edges against $4 \times 2 = 8$. The search checks, for every graph in the second class on up to six points, every subset of points, and finds that every one contains an overfull piece whose largest degree is the graph’s own. On graphs this small, being in the second class means having such a piece.

Random graphs almost never need the extra colour #

For random graphs the second class is rare and grows rarer: 3.0% at six points, 1.7% at seven, 0.3% at eight, and not one of the 1,200 random graphs on nine to twelve points. Paul Erdős and Robin Wilson proved in 1977 that almost every graph is in the first class. Their argument uses an earlier theorem of Jean-Claude Fournier: if no two points of largest degree are joined to each other, $\Delta$ colours suffice. A random graph almost always has a single point of largest degree, so Fournier’s theorem applies.

This is the opposite of the situation for colouring points, where a random graph needs about $n/(2\log_2 n)$ colours, far more than its largest clique, and pinning that number down is a hard problem in itself. For edges the trivial lower bound is almost always the exact answer.

Three edges at every point #

For graphs with three edges at every point — cubic graphs — the question is whether three colours suffice, and here the two classes connect to one of the most famous problems in mathematics. Peter Guthrie Tait observed in 1880 that the four colour theorem for maps is equivalent to the statement that every cubic graph that can be drawn in the plane without crossings, and has no single edge whose removal disconnects it, can have its edges coloured with three colours. Given four colours on the regions of a map, label them by the four elements of a group of two bits and colour each border by the sum of the two region labels; three non-zero sums give three edge colours. Running the construction backwards turns three edge colours into four region colours.

So a planar cubic graph in the second class would be a counterexample to the four colour theorem. Cubic graphs without such a bridge that need four colours exist, but none is planar; they are called snarks, after Lewis Carroll’s creature that hunters could never quite find, a name given by Martin Gardner in 1976. The Petersen graph is the smallest, and snarks of every even size from 18 points upward are known.

Why the classification is hard #

Ian Holyer proved in 1981 that deciding whether a cubic graph can be coloured with three colours on its edges is NP-complete — as hard as any problem whose solutions can be checked quickly. So there is, almost certainly, no efficient general test for which class a graph is in, though the answer is always one of two consecutive numbers. The search used here is exponential in the worst case, and it is fast on these graphs only because they are small or because a colouring is found quickly when one exists.

Overfullness is the one obstruction that is easy to test, and the overfull conjecture of Amanda Chetwynd and Anthony Hilton states that for graphs whose largest degree is more than a third of the number of points, it is the only obstruction: such a graph is in the second class exactly when it contains an overfull piece with the same largest degree. The census here is consistent with it on every graph up to six points, which is a check on small cases, not a proof. The Petersen graph shows the conjecture’s condition on the degree is needed: it has $\Delta = 3$ and ten points, three is less than a third of ten, and it is in the second class with no overfull piece at all.

A hard optimum never more than one away #

The theorem makes a hard-looking optimisation problem almost trivial to approximate: the trivial lower bound is never more than one short. And the one colour at stake is connected to two very different things. In the complete graphs it is arithmetic, whether the number of players is odd. In cubic planar graphs it is the four colour theorem. That the same single extra colour should separate tournament schedules for odd numbers of players from counterexamples to a century-old conjecture is the kind of unification that makes a classification worth having.

There is a practical reading too. Any problem that assigns time slots to pairs — exams sharing a student, matches sharing a team, data transfers sharing a link between two machines — is an edge colouring, with the slots as colours. Vizing’s theorem then says that the obvious lower bound, the busiest participant’s number of commitments, can always be met with at most one slot to spare, and the recolouring argument finds such a schedule quickly. For the vertex-colouring version of scheduling, where the conflicts are arbitrary, nothing remotely as good is possible.

Overfull pieces seen only to six points #

The census stops at six points, and the claim that every second-class graph there contains an overfull piece is a statement about those 207 graphs, not about graphs in general — the Petersen graph, at ten points, is a second-class graph with no overfull piece. The random graphs are 300 per size, enough to show the trend but not the exact rate at which the second class vanishes. And the figures do not show Vizing’s recolouring argument at work; they show its conclusion.

Colourings searched, Vizing’s proof quoted #

Computed here: the chromatic index of every graph drawn, by an exact backtracking search; the Petersen graph’s need for four colours and the complete graphs’ $n - 1$ or $n$ for 2 to 8 points; the circle-method schedules, checked to be proper; a bipartite graph coloured with $\Delta$ colours; every graph on up to six points up to isomorphism, with counts 1, 2, 4, 11, 34 and 156 checked against the known values, sorted by class, with every second-class graph found to contain an overfull piece; and the random graphs.

Quoted: Vizing’s theorem and its proof, König’s theorem, Fournier’s theorem and the result of Erdős and Wilson, Tait’s equivalence, Gardner’s naming of snarks, Holyer’s hardness theorem and the overfull conjecture.

Still open: the overfull conjecture #

Is every graph whose largest degree exceeds a third of its number of points in the second class exactly when it contains an overfull piece of the same largest degree? Chetwynd and Hilton conjectured this in 1986, and it is open. It would imply that for such graphs the class can be decided in polynomial time, by searching for an overfull piece, though the general problem is NP-complete. A special case about regular graphs, the 1-factorisation conjecture — that a regular graph on an even number of points whose degree is at least about half that number splits into perfect matchings — was proved for all large graphs in 2016 by Béla Csaba, Daniela Kühn, Allan Lo, Deryk Osthus and Andrew Treglown, by methods that give no information about small ones. That conjecture is the question behind every round-robin schedule for a league in which not every team meets every other.

The busiest point, plus one #

Every graph’s edges can be coloured with $\Delta$ or $\Delta + 1$ colours, where $\Delta$ is the most edges at any point, and which one is a hard question with a mostly simple answer. Bipartite graphs and complete graphs on an even number of points need only $\Delta$; complete graphs on an odd number need one more, because their edges overfill $\Delta$ colours. Every graph on up to six points that needs the extra colour contains an overfull piece, random graphs almost never need it, and a cubic planar graph that needed it would disprove the four colour theorem.