Every planar map is four colorable. (English) Zbl 0681.05027

Appel, Kenneth; Haken, Wolfgang

Contemporary Mathematics, 98. Providence, RI: American Mathematical Society (AMS). xv, 741 p. $ 80.00 (1989).

This volume contains corrected versions of the two papers [1] K. Appel and W. Haken [Ill. J. Math. 21, 429-490 (1977; Zbl 0387.05009)] and [2] K. Appel, W. Haken and J. Koch [ibid., 491-567 (1977; Zbl 0387.05010)], an appendix to [2], supplements to aid in the check of details of the proofs and the class check lists.
Moreover, a self-contained introduction to the history of the Four-Colour Problem and to the organization of the proof of the Four-Colour Theorem is included. Finding an unavoidable set of reducible configurations is sufficient for proving the Four-Colour Theorem. In [2] an unavoidable set of configurations is provided, and in [1] a discharging procedure is given. The method of discharging is the central element in the proof of the Four-Colour Theorem.
The appendix to [2] includes a polynomial time algorithm for four- colouring of planar maps.

Reviewer: U.Baumann

MSC:

05C15

Coloring of graphs and hypergraphs

Keywords:

vertex colouring; colouring algorithm; Four-Colour Theorem; planar maps

Citations:

Zbl 0387.05009; Zbl 0387.05010