Journal of Graph Algorithms and Applications
|Home||Issues||Aims and Scope||Instructions for Authors|
An Approximate Restatement of the Four-Color Theorem
Atish Das Sarma, Amita S. Gajewar, Richard L. Lipton, and Danupon Nanongkai
Vol. 17, no. 5, pp. 567-573, 2013. Concise paper.
Abstract The celebrated Four-Color Theorem was first conjectured in the 1850's. Since then there had been many partial results. More than a century later, it was first proved by Appel and Haken and then subsequently improved by Robertson et al. . These proofs make extensive use of computer for various computations involved. In mathematical community, there continues to be an interest for a proof that is theoretical in nature. Our result provides an interesting restatement of the Four-Color Theorem that requires only approximate colorings. Tait proved in 1880 that the Four-Color Theorem is equivalent to showing that two-edge connected, cubic, planar graphs have edge 3-colorings. Our main result is that this can be weakened to show that if there exists an approximate edge 3-coloring for these graphs, then the Four-Color Theorem is true.
Submitted: February 2013.
Reviewed: April 2013.
Revised: June 2013.
Accepted: June 2013.
Final: July 2013.
Published: July 2013.
Communicated by Dorothea Wagner