Das Vierfarbenproblem sagt bekanntlich, dass man jede Karte der Ebene mit vier Farben färben kann, so dass benachbarte Länder unterschiedliche Farben haben. Es wurde 1976 von Appel und Haken mit Computerhilfe bewiesen.
Ein schwierigeres Problem ist die auf Hadwiger und Nelson zurückgehende Frage, mit wievielen Farben man die Ebene einfärben kann, so dass es keine gleichfarbigen Punkte mit Abstand 1 gibt. (Hier ist also die Karte nicht vorgegeben, es wird nach einer beliebigen Zerlegung der Ebene mit möglichst wenig Farben gefragt.)
Wie im Bild oben angedeutet kann man die Ebene in Sechsecke vom Durchmesser o,99 zerlegen und auf diese Weise die Ebene mit sieben Farben färben, so dass Punkte im Abstand 1 jeweils unterschiedliche Farben haben.
Andererseits zeigt der im Bild oben eingezeichnete Graph, dass man mindestens 4 Farben braucht. Der Graph enthält vier gleichseitige Dreiecke der Kantenlänge 1, deren Ecken also jeweils mit 3 unterschiedlichen Farben gefärbt werden müßten. Mit nur 3 Farben wäre das aber nicht für alle 4 Dreiecke gleichzeitig möglich, außer wenn die fünfte (in keinem der Dreiecke enthaltene) Fünfecksseite mit zwei gleichen Farben gefärbt wäre. Diese Seite hat aber ebenfalls Länge 1.
Ein neuer Preprint von Grey beweist nun, dass auch 4 Farben nicht genügen, man also mindestens 5 Farben benötigt: https://arxiv.org/abs/1804.02385 Analog zum vorigen Beispiel konstruiert er ebenfalls einen Graphen mit vielen Kanten der Länge 1, den man jetzt nicht mit 4 Farben färben kann. Sein Graph ist freilich viel komplizierter, er hat 1567 Ecken.
Man darf gespannt sein, ob sich diese Zahl 1567 noch reduzieren läßt oder ob das das kleinstmögliche Gegenbeispiel ist.
Kommentare (4)