EINE KI WIDERLEGT EINE FÄRBUNGSVERMUTUNG AUS DEN 1990ERN

Man nehme ein Netz aus Punkten, die durch Linien verbunden sind — einen Graphen. Eine Totalfärbung gibt jedem Punkt und jeder Linie eine Farbe und folgt dabei drei Regeln: Zwei benachbarte Punkte unterscheiden sich, zwei Linien, die sich in einem Punkt treffen, unterscheiden sich, und eine Linie unterscheidet sich von ihren beiden Endpunkten. Die kleinste Farbanzahl, die funktioniert, heißt totalchromatische Zahl, geschrieben χ″(G).

Jetzt wird es schwieriger. Jeder Punkt und jede Linie bekommt eine eigene Liste erlaubter Farben, alle Listen gleich lang, nämlich k, und verlangt wird eine gültige Färbung aus diesen Listen. Das kleinste k, das für beliebige Listen funktioniert, ist die listen-totalchromatische Zahl χ″ℓ(G). Sie kann nie kleiner sein als χ″(G): Sind alle Listen gleich, landet man wieder beim gewöhnlichen Problem.

Eine Vermutung aus den späten 1990ern

Drei Gruppen — Borodin, Kostochka und Woodall; Juvan, Mohar und Škrekovski; Hilton und Johnson — schlugen in den späten 1990ern unabhängig voneinander vor, dass persönliche Listen nie etwas kosten:

χ″ℓ(G) = χ″(G) für jeden Graphen (sogar mit mehreren Linien zwischen zwei Punkten).

Das ist die Listen-Totalfärbungsvermutung (List Total Colouring Conjecture). Die Indizien sprachen für sie: Sie gilt für Graphen, in denen kein Punkt mehr als zwei Linien hat, und von jedem Graphen mit genau drei Linien pro Punkt (einem kubischen Graphen) war bekannt, dass er höchstens 5 Farben aus Listen braucht.

Das Gegenbeispiel

Jonathan Noel von der University of Victoria in Kanada präsentiert nun einen kubischen Graphen mit 20 Punkten, der χ″ = 4, aber χ″ℓ = 5 hat. Die Vermutung ist falsch.

Die Konstruktion ist kompakt. Man nehme vier Kopien eines kleinen Graphen namens K₂,₃: zwei „private“ Punkte, jeder mit denselben drei „Terminal“-Punkten verbunden. Dann verbinde man jedes Kopienpaar durch genau eine „Querlinie“ zwischen Terminals. Am Ende hat jeder Punkt drei Linien.

Der Graph G mit einer Totalfärbung in nur vier Farben, dargestellt durch Formen und Linienstile. — Abbildung 1, Noel (2026), arXiv:2609.38417.

Im gewöhnlichen Spiel genügen vier Farben: Farbe 4 geht an alle privaten Punkte und alle Querlinien, die einander nie berühren, und eine kleine Tabelle samt zyklischer Regel erledigt den Rest.

Listen, die sich nicht erfüllen lassen

Die Falle verwendet die Farben 1 bis 5. Jeder Punkt und jede Linie von Block i erhält die Liste „alle Farben außer i“; die Querlinien bekommen sorgfältig gewählte Listen, denen 5 oder i + 2 fehlt. Der Beweis läuft dann ab wie eine kurze Detektivgeschichte:

• Lemma: In jeder 4-Färbung von K₂,₃ müssen die beiden privaten Punkte dieselbe Farbe haben.
• Also hat jeder Block i ein Farbpaar {i, sᵢ}, und jede Querlinie zwischen zwei Blöcken muss eine Farbe verwenden, die beide Paare gemeinsam haben.
• Ein wenig Abzählen zeigt, dass eine Farbe t zu allen vier Paaren gehören muss.
• Für jedes mögliche t stellt eine bestimmte Querlinie fest, dass diese Farbe in ihrer Liste fehlt. Widerspruch.

Die Listenzuweisung: Jeder Punkt und jede Linie darf alle Farben von 1 bis 5 verwenden außer der angegebenen. Keine Totalfärbung kann diese Listen einhalten. — Abbildung 2, Noel (2026), arXiv:2609.38417.

Von einer Maschine gefunden, von einem Mathematiker geprüft

Das Paper ist ungewöhnlich offen über seine Herkunft. Am 24. September 2026 forderte Noel ChatGPT 6 Astra Ultra auf, die Vermutung zu widerlegen, und das Modell lieferte das Gegenbeispiel, „mit wenig Zutun des Autors“. Er prüfte die Argumente und schrieb den Text auf Grundlage der vom Modell erzeugten Entwürfe neu; das Modell half außerdem beim Korrekturlesen, schlug Literatur vor und zeichnete die Abbildungen. „Der Autor übernimmt die volle Verantwortung für die Korrektheit“, endet die Erklärung. Das Paper ist ein Preprint, doch der Beweis ist kurz genug, dass jede geduldige Leserin und jeder geduldige Leser ihn nachprüfen kann.

Eine Lücke von eins — oder mehr?

Persönliche Listen können eine zusätzliche Farbe kosten. Können sie mehr kosten? Eine Lücke von drei würde auch eine gut untersuchte Verwandte zu Fall bringen, die Listen-Kantenfärbungsvermutung, denn χ″ℓ ≤ χ′ℓ + 2 und χ″ ≥ χ′. Noel schließt mit einer offenen Frage, die das Gegenbeispiel der KI unberührt lässt: Gilt χ″ℓ(G) ≤ χ″(G) + 1 für jeden Graphen?