Hadwiger-Nelson-Problem

Das Hadwiger-Nelson-Problem ist ein nach Hugo Hadwiger und Edward Nelson benanntes Problem der Geometrischen Graphentheorie. Gesucht wird die minimal benötigte Anzahl an Farben, um eine Ebene derart einzufärben, dass jeweils zwei Punkte mit Abstand 1 unterschiedliche Farben besitzen. Das Problem konnte bisher nicht gelöst werden, gehört also zu den offenen Problemen der Mathematik, jedoch lässt sich die Lösung auf die Werte 5, 6 oder 7 einschränken. Die richtige Lösung hängt vermutlich davon ab, welche Axiome aus der Mengenlehre vorausgesetzt werden.

Das Problem lässt sich graphentheoretisch wie folgt formulieren: Sei G ein Einheitsdistanz-Graph in der Ebene, also ein unendlicher Graph, bei dem die Knoten mit den Punkten in der Ebene identisch sind. Außerdem sollen die Punkte genau dann durch eine Kante verbunden werden, wenn sie einen euklidischen Abstand von 1 besitzen. Dann besteht das Hadwiger-Nelson-Problem in der Bestimmung der chromatischen Zahl von G. Folglich wird das Problem auch häufig „Bestimmung der chromatischen Zahl in der Ebene“ genannt. Nach dem Satz von de Bruijn-Erdős ist das Problem (unter Annahme des Auswahlaxioms) äquivalent zur Bestimmung der größten chromatischen Zahl in einem endlichen Einheitsdistanz-Graphen.

Nach Jensen und Toft (1995) wurde das Problem bereits 1950 von Edward Nelson formuliert und von Martin Gardner 1960 zum ersten Mal veröffentlicht. Hadwiger hat 1945 gezeigt, dass jede Überdeckung der Ebene aus fünf kongruenten abgeschlossenen Mengen eine Kante mit Abstand 1 in einer ihrer Mengen enthält. Hadwiger erwähnte das Problem auch in einer späteren Veröffentlichung (1961). Das Problem und seine Geschichte wurden 2008 ausführlich von Soifer abgehandelt.