Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00304
An Approximate Restatement of the FourColor Theorem
Atish Das Sarma,
Amita S. Gajewar,
Richard L. Lipton, and
Danupon Nanongkai
Vol. 17, no. 5, pp. 567573, 2013. Concise paper.
Abstract The celebrated FourColor 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 FourColor Theorem that requires only approximate colorings. Tait proved in 1880 that the FourColor Theorem is equivalent to showing that twoedge connected, cubic, planar graphs have edge 3colorings. Our main result is that this can be weakened to show that if there exists an approximate edge 3coloring for these graphs, then the FourColor 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

Journal Supporters
