AN AI SINKS A 1990S COLOURING CONJECTURE

Take a network of points joined by lines — a graph. A total colouring gives a colour to every point and every line, following three rules: two neighbouring points differ, two lines meeting at a point differ, and a line differs from its two end points. The smallest number of colours that works is called the total chromatic number, written χ″(G).

Now make it harder. Give every point and every line its own list of allowed colours, all lists of the same size k, and demand a valid colouring picked from the lists. The smallest k that works whatever the lists is the list total chromatic number, χ″ℓ(G). It can never be smaller than χ″(G): if all lists are identical, you are back to the ordinary problem.

A conjecture from the late 1990s

Three groups — Borodin, Kostochka and Woodall; Juvan, Mohar and Škrekovski; Hilton and Johnson — proposed independently, in the late 1990s, that personal lists never cost anything:

χ″ℓ(G) = χ″(G) for every graph (even with multiple lines between two points).

This is the List Total Colouring Conjecture. Evidence supported it: it holds for graphs where no point has more than two lines, and every graph with exactly three lines per point (a cubic graph) was known to need at most 5 colours from lists.

The counterexample

Jonathan Noel, of the University of Victoria in Canada, now shows a cubic graph with 20 points that has χ″ = 4 but χ″ℓ = 5. The conjecture is false.

The construction is compact. Take four copies of a small graph called K₂,₃: two “private” points, each joined to the same three “terminal” points. Then link each pair of copies by exactly one “cross” line between terminals. Every point ends up with three lines.

The graph G with a total colouring in only four colours, shown by shapes and line styles. — Figure 1, Noel (2026), arXiv:2609.38417.

Four colours suffice in the ordinary game: colour 4 goes to all private points and all cross lines, which never touch each other, and a small table and a cyclic rule handle the rest.

Lists that cannot be satisfied

The trap uses colours from 1 to 5. Every point and line of block i gets the list “all colours except i”; the cross lines get carefully chosen lists missing 5 or i + 2. The proof then runs like a short detective story:

• Lemma: in any 4-colouring of K₂,₃, the two private points must have the same colour.
• So each block i has a pair of colours {i, sᵢ}, and every cross line between two blocks must use a colour shared by both pairs.
• A little counting shows one colour t must belong to all four pairs.
• For every possible t, one specific cross line finds that colour missing from its list. Contradiction.

The list assignment: each point and line may use every colour from 1 to 5 except the one indicated. No total colouring can respect these lists. — Figure 2, Noel (2026), arXiv:2609.38417.

Found by a machine, checked by a mathematician

The paper is unusually frank about its origin. On 24 September 2026, Noel prompted ChatGPT 6 Astra Ultra to disprove the conjecture, and it produced the counterexample, “with little input from the author”. He checked the arguments and rewrote the text from drafts the model generated; the model also helped proofread, suggested references and drew the figures. “The author takes full responsibility for correctness,” the declaration ends. The paper is a preprint, but the proof is short enough for any reader with patience to verify.

A gap of one, or more?

Personal lists can cost one extra colour. Can they cost more? A gap of three would also topple a well-studied relative, the List Edge Colouring Conjecture, because χ″ℓ ≤ χ′ℓ + 2 and χ″ ≥ χ′. Noel closes with an open question that the AI’s counterexample leaves standing: is χ″ℓ(G) ≤ χ″(G) + 1 for every graph?