An update on the four-color theorem. (English) Zbl 0908.05040

Thomas, Robin

Notices Am. Math. Soc. 45, No. 7, 848-859 (1998).

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

Keywords:

four-color theorem; history; apex; doublecross; Hadwiger’s conjecture

Citations:

Zbl 0331.05106; Zbl 0681.05027; Zbl 0883.05056; Zbl 0883.05055; Zbl 0830.05028