×

How false is Kempe’s proof of the four color theorem? II. (English) Zbl 1177.05038

Summary: [For part I see E. Gethner and W.M. Springer II, “How false is Kempe’s proof of the four color theorem?”, Congr. Numerantium 164, 159–175 (2003; Zbl 1050.05049).] We continue the investigation of A.B. Kempe’s flawed proof of the Four Color Theorem from a computational and historical point of view. Kempe’s “proof” gives rise to an algorithmic method of coloring plane graphs that sometimes yields a proper vertex coloring requiring four or fewer colors. We investigate a recursive version of Kempe’s method and a modified version based on the work of I. Kittell [“A group of operations on a partially colored map”, Bull. Am. Math. Soc. 41, 407–413 (1935; Zbl 0012.03501; JFM 61.1347.02)]. Then we empirically analyze the performance of the implementations on a variety of historically motivated benchmark graphs and explore the usefulness of simple randomization in four-coloring small plane graphs. We end with a list of open questions and future work.

MSC:

05C15 Coloring of graphs and hypergraphs
05C85 Graph algorithms (graph-theoretic aspects)
68R10 Graph theory (including graph drawing) in computer science
90C35 Programming involving graphs or networks
PDFBibTeX XMLCite
Full Text: DOI