The four-color problem. (English) Zbl 0149.21101

Ore, Øystein

Pure and Applied Mathematics. 27. New York-London: Academic Press. XV, 259 p. (1967).

Die Graphentheorie hat in den letzten Jahren an Bedeutung und allgemeinem Interesse zugenommen. Das vermeintlich tiefstliegende und zugleich aber auch verfänglichste Problem der Graphentheorie ist das berühmte (bis heute noch ungelöste) Vierfarbenproblem. Es besagt, in jedem ebenen Graphen \(G\) kann jede Ecke von \(G\) mit je einer Farbe immer so gefärbt werden, daß erstens je zwei benachbarte (d. h. durch eine Kante von \(G\) verbundene) Ecken von \(G\) stets mit zwei verschiedenen Farben gefärbt sind und man zweitens bei der Färbung aller Ecken von \(G\) mit 4 oder weniger Farben auskommt. Nach einem historischen Rückblick über das Vierfarbenproblem behandelt Verf. in den beiden ersten Kapiteln zunächst die ebenen Graphen, insbesondere ebene Dreiecksgraphen. Kapitel 3–5 machen den Leser mit einigen besonders interessanten Typen von Graphen bekannt: duale, paare (bipartite), reguläre Graphen, sowie Graphen, die eine Hamiltonsche Linie besitzen. In den Kapiteln 6–9 sind Färbungen von Graphen (Ecken-, Kanten- und Länder-Färbungen) behandelt. Sie vermitteln einen interessanten Einblick in die eigenartige Problematik der Färbungstheorie von Graphen. Im Kap. 10 erlebt der aufmerksame Leser eine große Überraschung. Das Vierfarbenproblem erscheint hier, losgelöst von der Ebene, als Teil eines allgemeinen Problems der Hadwiger-Vermutung. Die überaus reizvollen Begriffe der Graphentheorie: Homomorphis (subcontraction), simpliziale Zerfällungen von Graphen und Homomorphie-Basis, werden sehr ausführlich besprochen. Dem Studium eines weiteren sehr reizvollen Begriffs der Graphentheorie: kritische Graphen (critical graphs), ist Kap. 11 gewidmet. Schließlich befassen sich die letzten drei Kapitel 12–14 vorwiegend wieder mit ebenen Graphen. Zum Beispiel wird bewiesen, daß der Vierfarbensatz für alle ebenen Graphen mit höchstens 35 Ecken richtig ist.
Zusammenfassend möchte Ref. über das neue Buch des bekannten Verfassers sagen, daß hier ein ganz hervorragendes Werk über das Viefarbenproblem vorliegt. Es ist von Anfang bis Ende spannend und überaus klar geschrieben. Der Kenner des Vierfarbenproblems wird viele neue Anregungen finden. Aber auch der junge Studierende der Mathematik wird das Buch mit Erfolg lesen können und sehr bald seine Freude an den sinnreichen Methoden und Schlüssen der Graphentheorie haben. Ein reichhaltiges Schriftenverzeichnis, ein Namen- und Sachverzeichnis bilden den Abschluß des Buches.

Reviewer: K. Wagner

MSC:

05C15	Coloring of graphs and hypergraphs
05-02	Research exposition (monographs, survey articles) pertaining to combinatorics

Keywords:

topology