zbMATH — the first resource for mathematics

An update on the four-color theorem. (English) Zbl 0908.05040
K. Appel and W. Haken [Bull. Am. Math. Soc. 82, 711-712 (1976; Zbl 0331.05106)] announced a proof of the four-color theorem in 1976, providing an expanded version of that proof in 1989 [Every planar map is four colorable, Contemporary Mathematics 98, American Mathematical Society (1989; Zbl 0681.05027)]. In 1997, N. Robertson, D. Sanders, P. Seymour and R. Thomas published a greatly simplified proof; see [J. Comb. Theory, Ser. B 70, No. 1, 2-44 (1997; Zbl 0883.05056)]. In the present paper, the fourth of the latter authors summarizes the history of the theorem, gives several equivalent formulations (in a surprising variety of contexts, including vector cross products in $$\mathbb{R}^3$$, Lie algebras, and divisibility by 7), and discusses aspects of the new proof-including progress on some generalizations. To understand two recent results in this connection by N. Robertson, P. Seymour and R. Thomas [J. Comb. Theory, Ser. B 70, No. 1, 166-183 (1997; Zbl 0883.05055) and Combinatorica 13, No. 3, 279-361 (1993; Zbl 0830.05028)], define a graph $$G$$ to be apex if $$G\setminus v$$ is planar for some $$v$$ in $$V(G)$$ and doublecross if $$G$$ can be drawn in the plane with two crossings, both in the same region. Theorem 1. Let $$G$$ be a counterexample of minimum order to the conjecture that every cubic graph with no cut-edge and no edge 3-coloring has a Petersen minor; then $$G$$ is apex or doublecross. (The conjecture implies the four-color theorem.) Theorem 2. Let $$G$$ be a counterexample of minimum order to Hadwiger’s conjecture that if a graph has no $$K_6$$ minor, then it has a 5-coloring (another generalization of the four-color theorem); then $$G$$ is apex.
Reviewer: A.T.White (Oxford)

MSC:
 05C15 Coloring of graphs and hypergraphs
Full Text: