An Approximate Restatement of the Four-Color Theorem
Atish Das Sarma, Amita Surendra Gajewar, Richard L. Lipton, Danupon Nanongkai · Journal of Graph Algorithms and Applications · 2013
The celebrated Four Color Theorem was first conjectured in the 1850’s. More than a century later Appel and Haken [1] were able to find the first proof. Previously, there had been many partial results, and many false proofs. Appel and Haken’s famous proof has one “drawback”: it makes extensive use of computer computation. More recently Robertson, Sanders, Seymour and Thomas [18] created another proof of the Four Color Theorem. However, their proof, while simplifying some technical parts of the Appel-Haken proof, still relies on computer computations. There is some debate in the mathematical community about whether mathematicians should be satisfied with mathematical proofs that rely on extensive computation and there is interest in finding a new proof of the Four Color Theorem that relies on no computer computation. Such a proof would perhaps yield additional insights into why the Four Color Theorem is really true, and might yield new insights into the structure of planar graphs. In any case, there continues to be a search for such a proof. The contribution of this paper is that we initiate a new approach towards proving the Four Color Theorem. Our approach is based on insights from computer science theory and modern