Vier Farben reichen für jede Karte, sodass sich Nachbarn immer unterscheiden. Das wurde 1976 bewiesen. Aber wie findet man die Farben tatsächlich?
Das klassische Werkzeug ist die Kempe-Kette. Man wählt zwei Farben und nimmt das ganze zusammenhängende Ländergebiet in genau diesen Farben. Vertauscht man sie im ganzen Gebiet, bleibt die Karte korrekt gefärbt.
Der Haken: Ein einziger Tausch kann sich über die ganze Karte ausbreiten. Der bisherige Rekord brauchte mehr Tauschschritte, je größer die Karten wurden. Jeder kostete einen vollständigen Durchlauf über die Karte.
Sechs Mathematiker, von Tokio bis Kopenhagen, haben diesen Zusatzaufwand beseitigt. Ihr Algorithmus färbt n Länder in einer Zeit, die proportional zu n ist. Kleine Stücke der Karte werden einmal gelöst, in Tabellen gespeichert und dann einfach nachgeschlagen. Die Autoren nennen diese Geschwindigkeit optimal.
Quelle: Four-Coloring Planar Graphs in Linear Time, https://arxiv.org/abs/2610.39753










