imported>Schojoha: /* Literatur */

2025-09-30T17:39:02Z

Literatur

Neue Seite

[[Datei:Four Colour Map Example.svg|mini|hochkant|Beispiel einer Vier-Färbung]]
[[Datei:Map of United States vivid colors shown.svg|mini|Landkarte der amerikanischen Bundesstaaten mit vier Farben]]
Der '''Vier-Farben-Satz''' (auch '''Vier-Farben-Theorem''', früher auch als '''Vier-Farben-Vermutung''' oder '''Vier-Farben-Problem''' bekannt) ist ein [[Satz (Mathematik)|mathematischer Satz]] und besagt, dass vier Farben immer ausreichen, eine beliebige [[Karte (Kartografie)|Landkarte]] in der [[Euklidischer Raum|euklidischen Ebene]] so einzufärben, dass keine zwei angrenzenden Länder die gleiche Farbe bekommen. Der Satz findet Anwendung in der [[Graphentheorie]], [[Topologie (Mathematik)|Topologie]] und [[Kartografie]].

Dies gilt unter den Einschränkungen, dass isolierte gemeinsame Punkte nicht als „Grenze“ zählen und jedes Land aus einer zusammenhängenden Fläche besteht, also keine [[Exklave]]n vorhanden sind.

== Formalisierung ==
[[Datei:Four Colour Planar Graph.svg|mini|hochkant=1.5|Darstellung der Formulierung in der Graphentheorie]]
Formal lässt sich das Problem am einfachsten mit Hilfe der [[Graphentheorie]] beschreiben. Man fragt, ob die [[Knoten (Graphentheorie)|Knoten]] jedes [[Planarer Graph|planaren Graphen]] mit maximal vier Farben so [[Knotenfärbung|gefärbt]] werden können, dass keine zwei benachbarten Knoten die gleiche Farbe tragen. Oder kürzer: „Ist jeder planare [[Graph (Graphentheorie)|Graph]] [[Färbung (Graphentheorie)|4-färbbar]]?“ Dabei wird jedem Land der Karte genau ein Knoten zugewiesen und die Knoten angrenzender Länder werden miteinander verbunden.

== Geschichte ==
[[Datei:Fourcolorsmap.svg|mini|Diese Karte benötigt vier verschiedene Farben]]
Der Satz wurde erstmals 1852 von [[Francis Guthrie]] als [[Vermutung (Mathematik)|Vermutung]] aufgestellt, als er in einer Karte die Grafschaften von England färben wollte. Es war offensichtlich, dass drei Farben nicht ausreichten und man fünf in keinem konstruierten Beispiel brauchte. In einem Brief des Londoner Mathematikprofessors [[Augustus De Morgan]] vom 23. Oktober 1852 an den irischen Kollegen [[William Rowan Hamilton]] wurde die Vermutung erstmals diskutiert und veröffentlicht: „Genügen vier oder weniger Farben, um die Länder einer Karte so zu färben, dass benachbarte Länder verschiedene Farben tragen?“

Der englische Mathematiker [[Arthur Cayley]] stellte das Problem 1878 der mathematischen Gesellschaft Londons vor. Innerhalb nur eines Jahres fand [[Alfred Kempe]] einen scheinbaren Beweis für den Satz. Elf Jahre später, 1890, zeigte [[Percy Heawood]], dass Kempes Beweisversuch fehlerhaft war. Ein zweiter fehlerhafter Beweisversuch, 1880 von [[Peter Guthrie Tait]] veröffentlicht, konnte ebenfalls elf Jahre lang nicht widerlegt werden. Erst 1891 zeigte [[Julius Peter Christian Petersen|Julius Petersen]], dass auch Taits Ansatz nicht korrekt war. Heawood gab im Jahre 1890 mit der Widerlegung von Kempes „Vier-Farben-Beweis“ zusätzlich einen Beweis für den [[Fünf-Farben-Satz]] an, womit eine obere Schranke für die Färbung von planaren Graphen zum ersten Mal fehlerfrei bewiesen wurde. In Kempes fehlerhaftem Versuch steckten bereits grundlegende Ideen, die zum späteren Beweis durch Appel und Haken führten.

[[Heinrich Heesch]] entwickelte in den 1960er und 1970er Jahren einen ersten Entwurf eines [[Computerbeweis]]es, der aber mangels verfügbarer Rechenzeit nicht verwirklicht wurde.<ref name="Wilson">{{Literatur |Autor=Robin Wilson |Titel=Four Colors Suffice |Verlag=Princeton University Press |Ort=Princeton, NJ |Datum=2014 |Sammelwerk=Princeton Science Library |ISBN=978-0-691-15822-8}}</ref> Dieser konnte von [[Kenneth Appel]] und [[Wolfgang Haken]] an der [[University of Illinois at Urbana-Champaign|University of Illinois]] 1976 verbessert werden.<ref>{{Literatur |Autor=Gary Chartrand, Linda Lesniak |Titel=Graphs & Digraphs |Verlag=CRC Press |Datum=2005 |Seiten=221 |Sprache=en}}</ref><ref name="Wilson" /> Der Beweis reduzierte die Anzahl der problematischen Fälle von Unendlich auf 1936 (eine spätere Version sogar 1476), die durch einen Computer einzeln geprüft wurden. Nach Kritiken an diesem Beweis veröffentlichten Appel und Haken 1989 eine ausführliche Beschreibung mit einem 400-seitigen Anhang auf Mikrofilm.<ref>{{Literatur |Autor=Kenneth Appel, Wolfgang Haken (with the collaboration of J. Koch) |Titel=Every Planar Map is Four-Colorable |Sammelwerk=Contemporary Mathematics |Band=98 |Verlag=American Mathematical Society |Ort=Providence, RI |Datum=1989 |ISBN=0-8218-5103-9 |DOI=10.1090/conm/098}}</ref>

1996 konnten [[Neil Robertson (Mathematiker)|Neil Robertson]], [[Daniel Sanders (Mathematiker)|Daniel Sanders]], [[Paul Seymour (Mathematiker)|Paul Seymour]] und [[Robin Thomas (Mathematiker)|Robin Thomas]] einen modifizierten Computerbeweis finden,<ref name="RSST96">{{Literatur|Autor=Neil Robertson, Daniel P. Sanders, Paul Seymour, Robin Thomas |Titel=Efficiently four-coloring planar graphs |Sammelwerk= STOC’96: Proceedings of the twenty-eighth annual ACM symposium on Theory of computing |Verlag=ACM Press |Datum=1996 |Seiten=571–575 |DOI=10.1145/237814.238005 |Sprache=en}}</ref> der die Fälle auf 633 reduzierte. Auch diese mussten per Computer geprüft werden.

2005 haben Georges Gonthier und Benjamin Werner einen [[Formales System|formalen Beweis]] des Satzes in dem [[Theorembeweisen|Beweisassistenten]] [[Coq (Software)|Coq]] konstruiert.<ref>{{Literatur |Autor=Georges Gonthier |Titel=Formal Proof—The Four-Color Theorem |Sammelwerk=[[Notices of the American Mathematical Society]] |Band=55 |Jahr=2008|Online=https://www.ams.org/notices/200811/tx081101382p.pdf |Format=PDF |Nummer=11 |Seiten=1382–1393 |Sprache=en}}</ref>

== Kritik ==
Der Vier-Farben-Satz war das erste große mathematische Problem, das mit Hilfe von [[Computerbeweis|Computern gelöst]] wurde. Deshalb wurde der Beweis von einigen Mathematikern nicht anerkannt, da er nicht direkt durch einen Menschen nachvollzogen werden kann und da man sich auf die Korrektheit des [[Compiler]]s und der [[Hardware]] verlassen muss. Auch der Mangel an mathematischer Eleganz des Beweises wurde kritisiert. So äußerte schon im Jahre 1989 der Graphentheoretiker [[Horst Sachs]] explizit die Meinung, dass „die endgültige Lösung des Vierfarbenproblems noch aussteht“.<ref name="LV-1">Lutz Volkmann: ''Fundamente der Graphentheorie.'' 1996, S. 254–255.</ref> Die Kritik besteht auch in neuerer Zeit weiter und wurde etwa von dem britischen Mathematiker [[Ian Stewart (Mathematiker)|Ian Stewart]] bekräftigt.<ref name="IS-1">Ian Stewart: ''Die letzten Rätsel der Mathematik.'' 2015, S. 131–136.</ref>

[[Datei:FourColorsStamps.jpg|mini|[[Freistempel]] mit Zusatzinschrift ''Four colors suffice'', vom Mathematics Department der [[University of Illinois at Urbana-Champaign|UIUC]], an der Appel und Haken wirkten, nach dem Computerbeweis 1976 verwendet]]

== Beweisversuche ==
Einige bekannte [[Mathematiker]] haben sich an dem Beweis versucht. So berichtet [[Max Born]]<ref>Born: ''Erinnerungen an Hermann Minkowski zur Wiederkehr seines 50. Todestages.'' Die Naturwissenschaften, Band 46, 1959, S. 501</ref>, dass [[Hermann Minkowski]] (1864–1909) über mehrere Wochen einen Beweisversuch in einer Einführungsvorlesung für Topologie unternahm (mit den einführenden Worten, dies würde sich gut als Einführung in die Topologie eignen und daran hätten sich bisher nur Mathematiker dritten Ranges versucht), bis er schließlich aufgab. Born erinnert sich, dass damals ein Gewitter herrschte und Minkowski halb scherzhaft meinte, der Himmel zürne über seine Vermessenheit.

Auch [[Ernst Witt]] versuchte sich in den 1930er Jahren als Student an dem Beweis und präsentierte ihn [[Richard Courant]]; sein Freund [[Heinrich Heesch]] fand aber einen Fehler, was der Beginn dessen eigener Beschäftigung mit dem Problem war.

Andere Mathematiker, die sich mit dem Problem beschäftigten und bedeutende Teilresultate erzielten, waren [[Øystein Ore]] (der die Mindestanzahl der Gebiete, die mit vier Farben einfärbbar sind, auf 40 erhöhte) und [[Hassler Whitney]] (in seiner Dissertation aus 1932).

Es gibt auch algebraisch äquivalente Formulierungen ([[Howard Levi]], [[Juri Wladimirowitsch Matijassewitsch]], M. Mnuk, [[Noga Alon]]).<ref>{{Internetquelle |url=http://comet.lehman.cuny.edu/fitting/fourcolor/fourcolor.html |titel=Four Color Theorem |abruf=2022-06-12 |archiv-url=https://web.archive.org/web/20150212093832/http://comet.lehman.cuny.edu/fitting/fourcolor/fourcolor.html |archiv-datum=2015-02-12 |offline=ja }}</ref>

=== Kempes falscher Beweis ===
==== „Beweis“ ====
<gallery class="float-right">
Fall2 4 Nachbarn.svg|Fall 2 – v mit 4 Nachbarn in 4 Farben
Fall3 5 Nachbarn.svg|Fall 3 – v mit 5 Nachbarn in 4 Farben
</gallery>
[[Alfred Kempe]] versuchte 1879 als einer der ersten Mathematiker, einen Beweis des Vier-Farben-Satzes zu finden. Seine Idee, sogenannte Kempe-Ketten zu verwenden, findet sich noch heute im computergestützten Beweis wieder. Kempes Beweis war jedoch fehlerhaft, wie [[Percy Heawood]] 11 Jahre nach dessen Veröffentlichung feststellte. Der Beweis beruht auf einer Induktion über die Anzahl der Knoten des Graphen.

Zuerst lässt sich feststellen, dass nur [[Triangulierung (Topologie)|Triangulierungen]] beobachtet werden müssen. Andernfalls können wir Kanten hinzufügen, ohne neue Knoten zu definieren. Durch das Hinzufügen der Kanten wird die Komplexität der Färbung somit erhöht. Ist diese Triangulierung vierfärbbar, so ist es auch der zugrunde liegende Graph. Somit gehen wir [[ohne Beschränkung der Allgemeinheit]] davon aus, dass der zu färbende Graph <math>G</math> trianguliert ist.

Nach einer Folgerung aus dem [[Eulerscher Polyedersatz|Satz von Euler]] gibt es in planaren Graphen stets einen Knoten <math>v</math>, dessen Grad kleiner oder gleich fünf ist, also maximal fünf Nachbarn besitzt. Diesen Knoten entfernen wir im ersten Schritt und färben den Graphen <math>G\setminus v</math> mit vier Farben, was nach der Induktionsvoraussetzung möglich ist. Für Knoten <math>v</math> können nun nach dem Einfügen folgende drei Fälle auftreten:

# <math>v</math> besitzt drei oder weniger Nachbarn. In diesem Fall ist auf jeden Fall eine der vier Farben für <math>v</math> übrig, da in der Nachbarschaft maximal drei Farben benutzt werden konnten.
# <math>v</math> besitzt vier Nachbarn. Es ist davon auszugehen, dass diese in vier verschiedenen Farben gefärbt sind, sonst gehe zu Fall 1. Gehen wir davon aus, dass die Knoten <math>v_1</math> und <math>v_3</math> nicht durch eine grün-rote Kette verbunden sind, so können wir die Farben grün und rot in der Komponente von <math>v_1</math> tauschen. Wir färben also all diejenigen Knoten um, die auf einem Pfad im Graphen <math>G</math> liegen, der in <math>v_1</math> beginnt und nur rote oder grüne Knoten benutzt. Nach diesem Vorgehen ist der Knoten <math>v_1</math> in rot gefärbt. Da nun kein grüner Knoten in der Nachbarschaft von <math>v</math> mehr existiert, kann dieser grün gefärbt werden. Andernfalls muss eine Kette zwischen <math>v_1</math> und <math>v_3</math> existieren (siehe dafür Skizze Fall 2). Nach dem [[Jordanscher Kurvensatz|Jordanschen Kurvensatz]] kann es nun jedoch keine zweite Kette zwischen <math>v_2</math> und <math>v_4</math> geben. Dies bedeutet, <math>v_2</math> ist durch die rot-grüne Kette von <math>v_4</math> isoliert. Somit können mit analoger Argumentation die Farben blau und gelb im Teilgraphen getauscht werden, der <math>v_2</math> enthält. Demnach kann <math>v</math> in blau gefärbt werden.
# <math>v</math> besitzt fünf Nachbarn mit vier Farben. Wiederum werden Kempe-Ketten benutzt. Mit analogem Vorgehen zu Fall 2 existieren Ketten von <math>v_1</math> zu <math>v_3</math> und <math>v_4</math>. Andernfalls lässt sich <math>v_1</math> und die daran hängende Komponente in blau bzw. gelb umfärben, wodurch die Farbe rot für <math>v</math> frei werden würde. Nun wird jedoch der Knoten <math>v_2</math> von <math>v_4</math> isoliert. Dadurch kann <math>v_2</math> in gelb gefärbt werden, ohne dass <math>v_4</math> die Farbe ändert. Ebenfalls wird <math>v_5</math> von <math>v_3</math> isoliert, wodurch sich <math>v_5</math> blau färben lässt, ohne die Färbung von <math>v_3</math> zu ändern. Zusammenfassend wurde somit die Farbe grün aus der Nachbarschaft von <math>v</math> gelöscht, sodass dieser grün gefärbt werden kann.

In jedem Fall lässt sich also eine Farbe für den Knoten <math>v</math> finden, was den Induktionsbeweis abschließt.

==== Fehler im Beweis ====
<gallery class="float-right">
Errera.svg| Errera-Graph mit Kempe-Ketten
Errera gebrochen.svg|Errera-Graph mit gebrochenen Kempe-Ketten nach Farbenwechsel
</gallery>
Kempe übersah dabei, dass das Umfärben einer Komponente die isolierende Kette der anderen Komponente beschädigen kann. Als Beispiel dafür dient der [[Errera-Graph]] (Siehe Grafik rechts). Wir erhalten eine fehlerfreie induktive Färbung nach Kempes Methode bis zum Knoten 1. Bei diesem befinden wir uns im obigen Fall 3, Knoten 1 besitzt also fünf Nachbarn in vier Farben. Wir beobachten dabei ebenfalls die eben vorgestellten Kempe-Ketten (rot-blau von Knoten 5 zu 17, rot-gelb von Knoten 3 zu 17, siehe Skizze Errera-Graph). Dabei werden die beiden grünen Nachbarn isoliert. Knoten 12 ist hierbei getrennt vom gelben Knoten 3. Nach der Kempe-Methode wird somit Knoten 12 gelb gefärbt, was Knoten 7 in dessen Nachbarschaft ebenfalls umfärbt, wodurch dieser grün wird. Dieses Umfärben von Knoten 7 bricht nun die zweite beschützende rot-gelbe Kette. Knoten 10 ist nun nicht weiter von Knoten 5 isoliert und es entsteht eine grün-blaue Kette zwischen diesen beiden. Es ist also nicht möglich, Knoten 10 umzufärben, ohne die Farbe von Knoten 5 zu ändern. Somit befinden wir uns in derselben Situation wie zu Beginn, Knoten 1 besitzt fünf Nachbarn in vier Farben, wobei nun die Farbe gelb doppelt auftritt. Dadurch konnte keine Farbe für <math>v</math> freigemacht werden. Die Methode scheitert.

== Fehlerhafte Beweise und Gegenbeispiele ==
<gallery class="float-right">
4CT Non-Counterexample 1.svg|Diese Karte wurde mit fünf Farben eingefärbt, und man muss …
4CT Non-Counterexample 2.svg|… mindestens vier der zehn Regionen umfärben, um mit nur vier Farben auszukommen.
</gallery>

Wie viele offene Probleme der Mathematik hat der Vier-Farben-Satz eine Menge fehlerhafter Beweise und Gegenbeispiele provoziert. Es wurde hierbei versucht, Karten als Gegenbeispiel zum Vier-Farben-Satz zu konstruieren. Manche dieser Konstruktionen hielten der öffentlichen Prüfung über Jahrzehnte stand, bis sie als falsch erkannt wurden. Viele weitere, hauptsächlich von Amateuren entwickelte, sind niemals veröffentlicht worden.

Häufig enthalten die einfachsten „Gegenbeispiele“ eine Region, welche alle anderen Regionen berührt. Dies erzwingt eine Dreifärbung aller anderen Regionen, um die Vierfärbbarkeit der gesamten Karte zu gewährleisten. Die Gegenbeispiele übersehen dabei, dass durch Umfärbung des inneren Bereiches ebendieses erreicht werden kann, da sie sich zu sehr auf das äußere Gebiet stürzen.

Dieser Trick kann verallgemeinert werden; es ist leicht, Karten zu konstruieren, auf denen es unmöglich ist, mit vier Farben auszukommen, wenn die Farben einiger Regionen im Voraus festgelegt wurden. Ein oberflächlicher Überprüfer des Gegenbeispiels wird oft nicht daran denken, diese Regionen umzufärben.

Andere falsche Gegenbeweise verletzen die Annahmen des Satzes, wie zum Beispiel durch Verwendung von Regionen, die aus mehreren getrennten Bereichen bestehen, oder durch Verbieten von gleichfarbigen Regionen, die sich nur an einem Punkt berühren.

== Verallgemeinerungen ==
<gallery class="float-right" caption="Karte auf einem Torus, die sieben Farben benötigt">
Torus 7color.svg|Karte mit 7-Färbung in der Ebene dargestellt
Torus 7color animated.gif|Animierter [[Torus]] derselben Karte
</gallery>

Das Vier-Farben-Problem ist ein Spezialfall der [[Satz von Ringel-Youngs|Heawood-Vermutung]]. Das klassische Vier-Farben-Problem betrifft Landkarten, die auf einer Ebene oder Kugeloberfläche liegen. Die Heawood-Vermutung stellt die analoge Frage für allgemeine Oberflächen, etwa die [[Kleinsche Flasche]] (6 Farben), das [[Möbiusband]] (6 Farben), die [[Projektive Ebene]] (6 Farben) und den [[Torus]] (7 Farben). Interessanterweise ist die Verallgemeinerung – abgesehen vom Spezialfall für Ebenen oder Kugeloberflächen – wesentlich leichter zu beweisen als der Vier-Farben-Satz und kommt ohne Computerhilfe aus. J. W. Ted Youngs und [[Gerhard Ringel]] konnten im Jahr 1968 erstmals die Heawood-Vermutung für alle anderen Fälle beweisen ([[Satz von Ringel-Youngs]]). Der Vier-Farben-Satz wird also nicht durch diesen Beweis verifiziert, sondern muss gesondert behandelt werden.

Für geschlossene [[Orientierbare Mannigfaltigkeit|orientierbare]] oder nicht orientierbare Oberflächen mit positivem [[Geschlecht (Fläche)|Geschlecht]] hängt die maximal benötigte Anzahl <math>n</math> der Farben von der [[Euler-Charakteristik]] <math>\chi</math> der Oberfläche ab und beträgt

: <math>n = \left\lfloor\frac{7 + \sqrt{49 - 24 \chi}}{2}\right\rfloor</math>

wobei die Klammern die [[Abrundungsfunktion und Aufrundungsfunktion|Abrundungsfunktion]] bezeichnen.

Alternativ kann für [[Orientierbare Mannigfaltigkeit|orientierbare]] Oberflächen die Anzahl <math>n</math> der Farben abhängig vom [[Geschlecht (Fläche)|Geschlecht]] <math>g</math> der Oberfläche angegeben werden:<ref>Wolfram MathWorld: [https://mathworld.wolfram.com/MapColoring.html Map Coloring]</ref>

: <math>n = \left\lfloor\frac{7 + \sqrt{1 + 48g}}{2}\right\rfloor</math>

[[Datei:Vierfarbenproblem 3D.svg|mini|hochkant=1.5|Nach dem Zusammenfügen in der rechten Grafik sind jeweils die beiden gleichfarbigen „Riegel“ ''verbunden'' und bilden jeweils ''einen'' (L- bzw. X-förmigen) Körper. Da jeder Körper jeden anderen berührt, braucht man zum Färben so viele Farben wie Riegel (hier 8).]]
Erweitert man die Aufgabenstellung des Vier-Farben-Satzes von Oberflächen auf den dreidimensionalen euklidischen Raum, dann gibt es keine Obergrenze für die Anzahl der Farben. Anstelle der „Länder“ treten dreidimensionale Gebiete („Körper“) auf, die unterschiedliche Farben haben sollen, wenn sie eine gemeinsame [[Grenzfläche]] besitzen. Für jede Zahl <math>n</math> lässt sich ein Beispiel konstruieren ([[Heinrich Tietze]]), das mindestens <math>n</math> Farben benötigt. Man denke sich <math>n</math> „lange“ kongruente Quader („Riegel“) nebeneinanderliegend, die zusammen einen Quader quadratischer Grundfläche bilden. Darauf liegen noch einmal <math>n</math> zu den ersten kongruente Quader nebeneinander, aber senkrecht zu den unteren, so dass alle unteren Quader alle oberen Quader berühren. Nun sei jeder der unteren mit genau einem der oberen verbunden, so dass beide gemeinsam kreuzweise ''einen'' Körper bilden. Jeder dieser Körper berührt jeden anderen; man braucht also <math>n</math> Farben und <math>n</math> war beliebig.<ref>[[Christoph Scriba|Christoph Joachim Scriba]], Peter Schreiber: ''5000 Jahre Geometrie.'' 2. Auflage. Springer, Berlin 2005, ISBN 3-540-22471-8, S. 454 und Abb. 7.8.3</ref>

== Bemerkung ==
<gallery caption="Die Kuratowski-Minoren" class="float-right">
Graph K5.svg|Der <math>K_5</math>
Graph K3 3.svg|und der <math>K_{3,3}</math>
</gallery>

Wenn (so wie in der Realität häufig der Fall) ein Land auf mehrere nicht-angrenzende Gebiete verteilt ist ([[Kolonie]]n, [[Exklave]]n, …), dann ist der zugehörige Graph nicht notwendigerweise [[Planarer Graph|planar]] und es sind möglicherweise mehr als vier Farben zur Färbung notwendig. Auf Planarität kann man gegebene Graphen sehr schnell testen. Nach dem [[Satz von Kuratowski]] gibt es bestimmte Untergraphen, die die Planarität von Graphen verhindern. Es sind dies genau zwei Grundformen, die sogenannten Kuratowski-Minoren [[Vollständiger Graph|<math>K_5</math>]] und [[Vollständig bipartiter Graph|<math>K_{3,3}</math>]], und darüber hinaus ihre Unterteilungen. Durch eine geschickte Wahl der Datenstrukturen kann man diese „Untergraphen“ finden bzw. feststellen, dass es sie nicht gibt, indem man jeden Knoten und jede Kante nur konstant oft betrachtet.

Die kleinste mögliche Färbung in allgemeinen Graphen <math>G</math> zu finden, mit anderen Worten die sogenannte ''Chromatische Zahl'' <math>\chi(G)</math> zu bestimmen, ist eine sehr aufwändige Aufgabe (genauer: in ihrer Entscheidungsvariante [[NP-vollständig]]). Nach den [[Lemma von Tutte|Aussagen von Tutte]] wäre sie gelöst, wenn man im [[Dualgraph]]en <math>G^*</math> eine kleinste [[Gruppe (Mathematik)|Gruppe]] gefunden hat, sodass eine gruppenwertige Strömung (das ist ein „[[Flussproblem|Fluss]] ohne Anfang und Ende“), die nirgends das Nullelement annimmt, existiert. Diese [[Gruppenordnung]] heißt ''Flusszahl'' <math>\varphi(G^*)</math> und es ist für beliebige Graphen <math>\varphi(G^*)=\chi(G)</math>. Die Lösbarkeit dieses nach wie vor NP-vollständigen Problems ist unabhängig von der Struktur der vorgegebenen Gruppe und hängt nur von der Gruppenordnung ab.<ref>Weitere Aussagen und Sätze dazu in [[Reinhard Diestel]]: ''[ftp://ftp.math.ethz.ch/EMIS/monographs/Diestel/de/GraphentheorieIII.pdf Graph Theory.]'' Springer, 2000, ISBN 0-387-98976-5, S. 157 ff.</ref>

Es gibt weitere Zusammenhänge des Vier-Farben-Problems mit Problemen der [[Diskrete Mathematik|Diskreten Mathematik]], sodass man auch Methoden der [[Algebraische Topologie|Algebraischen Topologie]] anwenden kann.

== Zeitkomplexität ==
Eine 4-[[Färbung (Graphentheorie)|Färbung]] zu berechnen, ist für [[Planarer Graph|planare Graphen]] mit <math>n</math> [[Knoten (Graphentheorie)|Knoten]] in Zeit <math>O(n^2)</math> möglich.<ref name="RSST96" /> Dagegen ist die Entscheidung der Frage, ob auch drei Farben ausreichen, [[NP-Vollständigkeit|NP-vollständig]].<ref>Michael R. Garey, David S. Johnson: ''Computers and Intractability - A Guide to the Theory of NP-Completeness.'' W. H. Freeman, 1979. ISBN 0-7167-1045-5, S. 87ff.</ref>

== Literatur ==
* Neil Robertson, Daniel P. Sanders, Paul Seymour, Robin Thomas: ''[https://www.ams.org/era/1996-02-01/S1079-6762-96-00003-0/home.html A new proof of the four-colour theorem.]'' In: ''Electronic Research Announcements of the [[American Mathematical Society]].'' 2/1996. S. 17–25.
* Kenneth Appel, Wolfgang Haken: ''Every Planar Map is Four Colorable.'' In: ''Contemp. Math.'' vol. 98, Amer. Math. Soc., Providence, RI, 1989.
* Georges Gonthier: ''[https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/gonthier-4colproof.pdf A computer-checked proof of the Four Colour Theorem] (PDF; 607 kB).'' unveröffentlicht, dazu [https://www.ams.org/notices/200811/tx081101382p.pdf Gonthier: ''Formal proof- the four color theorem'', Notices AMS 2008] (PDF; 2,6 MB).
* [[Rudolf Fritsch (Mathematiker)|Rudolf Fritsch]], Gerda Fritsch: ''Der Vierfarbensatz: Geschichte, topologische Grundlagen und Beweisidee.'' BI-Wissenschaftsverlag, 2004, ISBN 3-411-15141-2 ([https://epub.ub.uni-muenchen.de/4494/1/4494.pdf PDF]).
* Robin Thomas: ''An update on the four color theorem.'' Notices AMS 1998, Heft 7 ([https://www.ams.org/notices/199807/thomas.pdf PDF]).
* {{Literatur
|Autor=[[Gerhard Ringel]]
|Titel=Das Kartenfärbungsproblem
|TitelErg=In: Selecta Mathematica III (Hrsg. Konrad Jacobs)
|Reihe=Heidelberger Taschenbücher
|BandReihe=86
|Verlag=Springer
|Ort=Berlin, Heidelberg, New York
|Datum=1971
|ISBN=3-540-05333-6
|Online=[https://mathscinet.ams.org/mathscinet/search/publdoc.html?arg3=&co4=AND&co5=AND&co6=AND&co7=AND&dr=all&pg4=AUCN&pg5=TI&pg6=PC&pg7=ALLF&pg8=ET&r=1&review_format=html&s4=Ringel&s5=Kartenf%C3%A4rbungsproblem&s6=&s7=&s8=All&sort=Newest&vfpref=html&yearRangeFirst=&yearRangeSecond=&yrop=eq MR0543809]}}
* {{Literatur
|Autor=[[Ian Stewart (Mathematiker)|Ian Stewart]]
|Titel=Die letzten Rätsel der Mathematik
|TitelErg=rororo 61694
|Kapitel=4
|Auflage=2.
|Verlag=Rowohlt Taschenbuch Verlag
|Ort=Reinbek bei Hamburg
|Datum=2015
|ISBN=978-3-499-61694-5}}
* {{Literatur |Autor=Lutz Volkmann |Titel=Fundamente der Graphentheorie |Verlag=Springer Verlag |Ort=Wien, New York |Datum=1996 |ISBN=3-211-82774-9 |Online=[https://mathscinet.ams.org/mathscinet/search/publdoc.html?arg3=&co4=AND&co5=AND&co6=AND&co7=AND&dr=all&pg4=AUCN&pg5=TI&pg6=PC&pg7=ALLF&pg8=ET&review_format=html&s4=Volkmann%2C%20Lutz&s5=&s6=&s7=&s8=All&sort=Newest&vfpref=html&yearRangeFirst=&yearRangeSecond=&yrop=eq&r=364&mx-pid=1392955 MR1392955]}}
* [[Robin Wilson (Mathematiker)|Robin Wilson]] ''Four colours suffice.'' Princeton University Press 2002, [https://www.ams.org/notices/200402/rev-toft.pdf Review in den Notices AMS, 2004, PDF-Datei]

== Weblinks ==
{{Commonscat|Four-color theorem|Vier-Farben-Satz}}
* [https://www.math.gatech.edu/~thomas/FC/fourcolor.html Zusammenfassung des Beweises von Robertson, Sanders, Seymour, Thomas] auf der Homepage von Robin Thomas (englisch)
* [https://www.chiark.greenend.org.uk/~sgtatham/puzzles/ Simon Tatham’s Portable Puzzle Collection] Das Spiel ''Map'' behandelt das Thema.
* [https://homepages.math.uic.edu/~kauffman/MapReform.pdf Reformulating the Map Color Theorem von Louis H. Kauffman] (PDF; 589 kB). Umformulierung des Vierfarbproblems unter Berücksichtigung von George Spencer-Browns Lösungsansatz in Laws of Form (englisch)

== Einzelnachweise ==
<references />

{{SORTIERUNG:VierFarbenSatz}}
[[Kategorie:Topologische Graphentheorie]]
[[Kategorie:Kartografie]]
[[Kategorie:Satz (Graphentheorie)]]

Vier-Farben-Satz - Versionsgeschichte

imported>Schojoha: /* Literatur */