Gethner, Ellen; Kallichanda, Bopanna; Mentis, Alexander S.; Braudrick, Sarah; Chawla, Sumeet; Clune, Andrew; Drummond, Rachel; Evans, Panagiota; Roche, William; Takano, Nao How false is Kempe’s proof of the four color theorem? II. (English) Zbl 1177.05038 Involve 2, No. 3, 249-265 (2009). 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 Keywords:four color theorem; Kempe; Kittell Citations:Zbl 1050.05049; Zbl 0012.03501; JFM 61.1347.02 PDFBibTeX XMLCite \textit{E. Gethner} et al., Involve 2, No. 3, 249--265 (2009; Zbl 1177.05038) Full Text: DOI