An Approximate Restatement of the Four-Color Theorem

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.