1968 bewiesen Ringel und Young die Heawood-Vermutung für Flächen höheren Geschlechts, also die Formel für die Anzahl benötigter Farben in Abhängigkeit vom Geschlecht. Beispielsweise braucht man – was schon Heawood bewiesen hatte – immer sieben Farben, um eine Karte auf dem Torus zu färben.
Zum klassischen Vier-Farben-Problem in der Ebene hatte seit den 30er Jahren aber eigentlich nur noch Heinrich Heesch gearbeitet. Er war in Göttingen Assistent von Hermann Weyl gewesen, hatte damals über Gruppen und Ornamente gearbeitet und als Reaktion auf die politischen Säuberungen 1933 seine Stelle an der Universität aufgegeben, dann bis einige Jahre nach dem Krieg als Privatgelehrter im Kieler Haus seiner Eltern gewohnt. Neben anderen Forschungen hatte er schon vor dem Krieg als erster den ursprünglichen Ansatz im Vier-Farben-Problem wieder aufgenommen und große Fortschritte sowohl im Reduzibilitätsaspekt wie in der Analyse unvermeidlicher Mengen erzielt. (Über die Struktur eines minimales Gegenbeispiel war durch Birkhoff einiges bekannt: jede Ecke hat Grad mindestens 5, nach Polyederformel gibt es mindestens 12 Ecken von Grad 5, also mindestens so viele wie im Gerüstgraph des Ikosaeders, es gibt keinen trennenden Graph der Länge < 5 und bei einem trennendem Kreis der Länge 5 ist eines der Gebiete nur eine Ecke. Gesucht war in Birkhoffs Programm dann eine unvermeidbare Menge reduzierbarer Konfigurationen. Eine Reihe von Arbeiten hatten reduzierbare Konfigurationen gefunden, aber man war weit entfernt von einer unvermeidbaren Menge.) Heesch war bald klar geworden, dass eine unvermeidliche Menge möglicherweise tausende, jedenfalls zu viele, Konfigurationen enthalten musste, um ohne Rechenhilfe bewältigt werden zu können. Demzufolge wurde die Geschichte des Vier-Farben-Problems eine Geschichte der Entwicklung von Hochleistungsrechnern. Nachdem er eine Lehrtätigkeit an der Technischen Hochschule Hannover aufgenommen hatte, leistete Heesch später auch grundlegende Beiträge zu einer computergestützten Lösung des Vier-Farben-Problems. Gelöst wurde das Problem aber nicht von ihm, sondern von Appel und Haken. Haken, der die Theorie der Normalflächen in der dreidimensionalen Topologie eingeführt und unter anderem einen theoretischen Algorithmus zur Klassifikation von Haken-Mannigfaltigkeiten entwickelt hatte, trug zur Lösung des Vier-Farben-Problems die konzeptionellen Ideen bei, während Appel den Großteil der Programmierung durchführte. In ihrem ersten Beweis fanden sie 1825 unvermeidbare Strukturen, in einer späteren Version kamen sie mit 1478 aus. Der Beweis der Unvermeidbarkeit dieser Strukturen kam durch massiven Computereinsatz zustande und konnte nur per Computer verifiziert werden. Sie benötigten 1200 Stunden Rechenzeit auf einer IBM 360 mit 64 kB Arbeitsspeicher - solche Ressourcen hatte Heesch in Hannover nicht zur Verfügung gehabt. Die Universität Illinois brachte zur Feier des Beweises einen Poststempel "Vier Farben genügen!" heraus. 1996 fanden Robertson, Sanders, Seymour und Thomas einen Beweis mit ‘nur’ 633 unvermeidbaren Strukturen, der aber auch nur von einem Computer geprüft werden kann. Trotz seiner Bekanntheit nimmt das Vier-Farben-Problem eine einsame Stelle in der Mathematik ein, weil der Beweis unangemessen lang und ohne Beziehungen zu anderen Teilen der Mathematik ist. Bild: https://commons.wikimedia.org/wiki/File:Wolfgang_Haken_2008.jpg
Kommentare (7)