List Total Colouring Conjecture (late 1990s) disproved; counterexample found by ChatGPT 6 Astra Ultra 'with little input'
On Sept 29, 2026 Jonathan A. Noel posted a 20-vertex cubic graph whose total chromatic number is 4 but whose list total chromatic number is 5. This disproves the List Total Colouring Conjecture of Borodin–Kostochka–Woodall, Juvan–Mohar–Škrekovski and Hilton–Johnson from the late 1990s. The paper's AI declaration says Noel prompted ChatGPT 6 Astra Ultra on Sept 24 to disprove the conjecture and it produced the counterexample; Noel checked the arguments and rewrote the exposition. It is his second list-colouring conjecture disproof by Astra Ultra in September, after the Partial List Colouring Conjecture.
Key facts
- Result: a cubic simple graph G on 20 vertices (four copies of K_{2,3} joined by one cross edge between each pair) with χ''(G) = 4 and list total chromatic number χ''_ℓ(G) = 5 (arXiv 2609.38417 abstract and Section 2)
- Conjecture disproved: the List Total Colouring Conjecture (list total chromatic number = total chromatic number for every multigraph), posed independently by Borodin–Kostochka–Woodall, Juvan–Mohar–Škrekovski and Hilton–Johnson in the late 1990s
- AI declaration (verbatim): 'On September 24, 2026, the author prompted ChatGPT 6 Astra Ultra to disprove the List Total Colouring Conjecture and it produced the counterexample in this paper. The author checked the arguments and rewrote the exposition based on drafts generated by ChatGPT ... The figures were also generated by ChatGPT. The author takes full responsibility for correctness.'
- Abstract: 'ChatGPT 6 Astra Ultra discovered the counterexample with little input from the author.'
- Noel asks whether χ''_ℓ(G) ≤ χ''(G) + 1 might still hold for all multigraphs
- Same author, same model, same month: Noel's arXiv 2609.23291 disproved the Partial List Colouring Conjecture (Albertson–Grossman–Haas) with a counterexample 'discovered and fully verified by ChatGPT 6 Astra Ultra after some persistent prompting'
- Verification status: unrefereed arXiv preprint (math.CO); the proof is short and hand-checkable; no Lean formalisation mentioned. No HN thread or high-reach X post found as of Oct 5
Science result
- Field
- mathematics / graph theory (list colouring, total colouring)
- Problem
- List Total Colouring Conjecture (Borodin–Kostochka–Woodall; Juvan–Mohar–Škrekovski; Hilton–Johnson) (open since 1997)
- Result
- Disproved: an explicit 20-vertex cubic graph with total chromatic number 4 and list total chromatic number 5.
- AI system
- GPT-6 Astra Ultra
- Human role
- AI-found counterexample: the author prompted the model to disprove the conjecture; he checked the proof and rewrote the drafts
- Verification
- Unrefereed preprint; short explicit proof checked by the author
- Status
- pending
- Why surprising
- A well-known graph-colouring conjecture from the late 1990s fell to a single prompted search, with a counterexample small enough to draw.
What happened
Jonathan A. Noel posted "The List Total Colouring Conjecture is False" to arXiv (math.CO) on Sept 29, 2026. The total chromatic number χ''(G) is the fewest colours needed to colour both the vertices and the edges of a graph so that adjacent or incident elements differ. The list version gives every vertex and edge its own list of allowed colours. The List Total Colouring Conjecture, posed independently by three groups in the late 1990s, says the list version never needs more colours than the ordinary one.
The counterexample is a cubic graph on 20 vertices. It is built from four disjoint copies of K_{2,3}, with exactly one edge between each pair of copies. It has a total colouring with 4 colours, but Noel gives a list assignment from {1,…,5} with 4 colours per element that admits no proper colouring. So the list total chromatic number is 5.
The paper's AI declaration says Noel prompted ChatGPT 6 Astra Ultra on Sept 24, 2026 to disprove the conjecture, and the model produced the counterexample. The author checked the arguments, rewrote the exposition from ChatGPT drafts and used ChatGPT to proofread, suggest references and generate the figures.
Why it matters
This is a named conjecture from the late 1990s, listed on Open Problem Garden, falling to a prompted AI search, with a counterexample small enough to verify by hand. Together with Noel's Partial List Colouring disproof earlier in September, it is a clear case of a frontier model finding counterexamples to long-standing graph-colouring conjectures with little human guidance. It remains an unrefereed preprint.
Changelog
- 2026-10-05: created (12:30 quick run, from the sweep's arXiv AI-disclosure list; PDF AI declaration read)
Related events
- Summer 2026 flood: dozens of named conjectures settled on arXiv with disclosed AI help (July–September catalogue) ★★★★
- OpenAI releases GPT-6 Astra, its first GPT-6 model ★★★★★
Sources (3)
- paperarXiv 2609.38417: The List Total Colouring Conjecture is False (Noel)
- paperarXiv 2609.23291: The Partial List Colouring Conjecture is False (Noel)
- discussionOpen Problem Garden: List Total Colouring Conjecture
id: 2026-09-29-list-total-colouring-conjecture-false-astra · updated 2026-10-05 · open in the interactive timeline