4E86CD81-62F3-48ED-9EB2-B195BBB44B22

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.

D16AD7EB-86F9-4123-8953-B1CD1C1DF478

Kommentare (4)

  1. #1 Aveneer
    11. April 2018

    Ich sehe da vor allem in der Mitte eine Person mit Brille, die trotz Ihrer vielen Kanten und Ecken lächeln zu scheint.

  2. #2 rolak
    11. April 2018

    vor allem

    Oder MickeyMouse, Aveneer.

    gespannt

    Das zu sehende Muster ist ja bereits eine ~13fach reduzierte Ausgabe des originalen GegenbeispielGraphs, wenn ich die Arbeit richtig verstanden habe. Deren Ende wirkte auch eher wie ein cliffhanger statt wie ein großes Finale.

  3. #3 volki
    16. April 2018
  4. […] Farben einfärben kann, dass es keine gleichfarbigen Punkte vom Abstand genau 1 gibt. (Wir hatten hier darüber […]