VIER FARBEN FÜR JEDE KARTE, GEFUNDEN IN LINEARER ZEIT

Jede auf ein flaches Blatt gezeichnete Karte lässt sich mit vier Farben so färben, dass benachbarte Länder nie dieselbe haben. Francis Guthrie vermutete es 1852; Appel und Haken bewiesen es 1976. Doch der Satz sagt nur, dass vier Farben existieren. Wie findet man sie für eine gegebene Karte? „Darauf gibt es keine einfache Antwort“, schreiben Yuta Inoue von der Universität Tokio und fünf Kollegen aus Japan, Kanada, Slowenien und Dänemark. Die Frage war so verwickelt, dass sie zu vielen vermeintlichen Gegenbeispielen führte.

Punkte, Linien und Dreiecke

Jedes Land wird zu einem Punkt, einem Knoten, und jede gemeinsame Grenze zu einer Linie, einer Kante: Die Karte wird zu einem planaren Graphen, gezeichnet ohne sich kreuzende Linien. Ihn zu färben heißt, jedem Knoten eine von vier Farben zu geben, verschieden an den beiden Enden jeder Kante. Nennen wir n die Zahl der Knoten. Es genügt, Triangulierungen zu behandeln, in denen jede Fläche ein Dreieck ist: Mehr Kanten machen das Färben nur schwieriger.

Kempes Tausch

Der Grundzug geht auf eine Arbeit von A. B. Kempe aus dem Jahr 1879 zurück. Man bilde Paare aus den vier Farben, etwa Rot mit Blau und Grün mit Gelb. Eine Kempe-Kette ist eine zusammenhängende Gruppe von Knoten, die die beiden Farben eines Paares tragen. Vertauscht man diese beiden Farben entlang einer ganzen Kette, bleibt die Färbung gültig.

Man nehme einen Knoten v mit vier Nachbarn, v0 bis v3 der Reihe nach um ihn herum, und färbe zuerst den Rest. Verwenden die Nachbarn drei Farben oder weniger, erhält v die freie. Verwenden sie alle vier, folgt man der Kette, die bei v0 in den Farben von v0 und v2 beginnt. Erreicht sie v2 nicht, vertauscht man sie: v0 nimmt die Farbe von v2 an, wodurch eine für v frei wird. Erreicht sie v2 doch, vertauscht man stattdessen die Kette von v1 in den Farben von v1 und v3, sodass v1 die Farbe von v3 annimmt.

Stücke, die sich immer reparieren lassen

Beweise des Satzes beruhen auf reduziblen Konfigurationen: kleinen Mustern, die sich herausschneiden und wieder einsetzen lassen, sobald der Rest gefärbt ist. Passen die Farben ihres Rings – der Knoten unmittelbar um sie herum – nicht, so behebt eine beschränkte Zahl verbessernder Kempe-Änderungen außerhalb davon das immer: höchstens 25 für die hier verwendeten Muster, deren Ringe höchstens 18 Knoten haben.

Ein kleiner Graph aus sieben mit Zahlen beschrifteten Punkten und derselbe Graph, umgeben von einem größeren Netz aus Dreiecken.

Eine reduzible Konfiguration (links; jede Zahl gibt an, wie viele Nachbarn dieser Knoten in der vollständigen Karte haben muss) und dasselbe Muster, ergänzt durch seinen Ring R (rechts). — Abbildung 1, Inoue et al. (2026), arXiv:2610.39753.

Robertson, Sanders, Seymour und Thomas zeigten 1997, wie man auf diese Weise färbt, ein Muster nach dem anderen. Jede Runde verkleinert den Graphen um einige Knoten und kostet einen Durchlauf über den ganzen Graphen, sodass die Zeit quadratisch ist: viermal länger für eine doppelt so große Karte.

In einer früheren Arbeit (FOCS’26) bewiesen dieselben sechs Autoren, dass jede Triangulierung eine zu n proportionale Zahl sich nicht berührender reduzibler Konfigurationen enthält, entnommen aus einer Liste von 8.202 – oder ebenso viele kurze Schleifen mit Knoten auf beiden Seiten, die ebenfalls helfen. Sie entfernen alle Muster auf einmal, färben den Rest und reparieren dann alle Ringe zusammen. Eine zufällige Kempe-Änderung hilft einem bestimmten Ring, wenn sie die richtige Paarung der Farben wählt (eine Chance unter drei) und bei jeder Kette, die den Ring berührt, den richtigen Münzwurf trifft (jeweils eine Chance unter zwei). Bei bis zu 18 solchen Ketten ist das mindestens eine Chance unter 3 × 2¹⁸, also 786.432: klein, aber fest. Daher wächst die Zahl der Runden nur wie log n, ungefähr die Zahl der Male, die sich n halbieren lässt. Doch eine einzige Änderung kann einen konstanten Bruchteil des Graphen betreffen: Jede kostet einen vollständigen Durchlauf, insgesamt n log n.

Eine Tabelle statt eines Durchlaufs

Die neue Arbeit behält die log n Änderungen bei, macht aber jede einzelne billiger. Nach einer Vorbereitung, die eine zu n proportionale Zeit dauert, wird jede Änderung im Schnitt in etwa n / log n Schritten gefunden und ausgeführt. Die log n Änderungen zusammen brauchen dann eine zu n proportionale Zeit – lineare Zeit –, eine Schranke, die die Autoren optimal nennen.

Der Trick ist die „Methode der vier Russen“ (Method of Four Russians). Ein Teilproblem, das in einen Code von ½ log n Bits passt – die Hälfte der Binärziffern, die man zum Schreiben von n braucht –, hat höchstens √n mögliche Varianten, sodass sich alle ihre Antworten im Voraus berechnen und in einer Tabelle speichern lassen. Der angenommene Computer, mit Speicherwörtern von etwa log n Bits, liest jede gespeicherte Antwort in einem Schritt.

Der Graph wird immer wieder in verschachtelte Regionen mit kurzen Grenzen zerlegt. Die kleinsten enthalten etwa log n Knoten und passen samt Farben in einen einzigen Code. Für jede Region hält ein kleiner Übersichtsgraph fest, welche Grenzknoten eine Kempe-Kette teilen. Eine Änderung wandert dann als Folge von „Tauschen“- oder „Behalten“-Bits nach unten, und in jeder kleinen Region aktualisiert ein einziges Nachschlagen jede Farbe.

Ein mit roten, blauen, grünen und gelben Punkten gefärbter Graph, mit einer grau umrandeten Region und einigen dick schwarz gezeichneten Kanten.

Teil eines mit vier Farben gefärbten Graphen. Die graue Fläche ist eine Region R; dicke schwarze Kanten gehören zu den Kempe-Ketten der Paare Rot-Blau und Grün-Gelb. — Abbildung 2, Inoue et al. (2026), arXiv:2610.39753.

Derselbe Regionsumriss, dessen Grenzpunkte durch dünne blaue Linien mit einigen hellblauen Flecken verbunden sind.

Die Übersicht derselben Region: Jeder blaue Fleck steht für ein Stück einer Kempe-Kette, und seine Linien zeigen, welche Grenzknoten es verbindet. — Abbildung 3, Inoue et al. (2026), arXiv:2610.39753.

Wählen ohne Würfel

Mit zufälligen Entscheidungen färbt dies eine Karte bereits im Schnitt in linearer Zeit. Die Würfel ohne Geschwindigkeitsverlust zu entfernen, war „bei Weitem der schwierigste Teil“. Man nenne einen Ring lebendig, solange jede bisherige Entscheidung zu seinen Gunsten ausfiel. Würden die u noch nicht entschiedenen Ketten, die ihn berühren, Münzwürfen überlassen, überlebte er mit Wahrscheinlichkeit 1/2^u; summiert über alle lebendigen Ringe ergeben diese Zahlen die erwartete Zahl der Überlebenden. Die Entscheidung über eine Kette verdoppelt den Term jedes Rings, der diese Wahl wollte, und setzt die anderen auf null. Der Algorithmus wählt die Option, die die Summe nicht sinken lässt, sodass am Ende mindestens so vielen Ringen geholfen ist, wie der Zufall im Schnitt geholfen hätte.

Eine Schranke, keine Stoppuhr

Die Arbeit berichtet weder über eine Implementierung noch über eine Laufzeit, und die in „proportional zu n“ verborgenen Konstanten werden nicht angegeben. Sie sind groß: Für jedes der 8.202 Muster speichert der Algorithmus, wie viele verbessernde Änderungen jede Färbung seines Rings braucht – „eine riesige konstante Menge an Information“. In einem Anhang korrigieren sie zudem „einen kleinen Fehler“ in einer Konstruktion verschachtelter Regionen von 2013, auf der sie aufbauen. Zu einer Vermutung von 1852 gibt es nun ein Färbeverfahren, dessen Aufwand nicht schneller wächst als die Karte, die es färbt.