How false is Kempe’s proof of the Four Color Theorem? Part II

2009/10/03 by Ellen Gethner, Bopanna Kallichanda, Alexander S. Mentis +7 · 2 citations
Decision Sciences · Engineering · Computer Science · #Scheduling and Timetabling Solutions #graph theory and CDMA systems #Advanced Graph Theory Research

paper · pdf · doi:10.2140/involve.2009.2.249

openalex publication_date 2009/10/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11

Abstract

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. 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.

Citations

• The Solution of the Four-Color-Map Problem
• The Four-Colour Theorem
• On the Geographical Problem of the Four Colours

Cited by

• Four color theorem [wikipedia]
• Triaugmented triangular prism [wikipedia]