Mathematical Proofs of Two Conjectures: The Four Color Problem and The Uniquely 4-colorable Planar Graph

2009/11/09 by Jin Xu, Xu, Jin · 1 voice · 1 citation
Computer Science · Mathematics · #05C10 #05C15 #05C31 #Advanced Graph Theory Research #Combinatorics #Computational Geometry and Mesh Generation #Computer graphics (images) #Computer science #Conjecture #Discrete mathematics #FOS: Mathematics #General Mathematics (math.GM) #Geometry #Graph #Graph Labeling and Dimension Problems #Graph coloring #Mathematical proof #Mathematics #Planar #Planar graph #Vertex (graph theory) #math.GM #msc:05C10 #msc:05C15 #msc:05C31

paper · pdf · doi:10.48550/arxiv.0911.1587

published in arXiv (Cornell University) (Cornell University) · 145 pages, 289 figures

openalex publication_date 2009/11/09 · arxiv created 2012/01/18 · arxiv updated 2015/03/13 · openalex created_date 2016/06/24 · openalex updated_date 2026/08/05

Abstract

The famous four color theorem states that for all planar graphs, every vertex can be assigned one of 4 colors such that no two adjacent vertices receive the same color. Since Francis Guthrie first conjectured it in 1852, it is until 1976 with electronic computer that Appel and Haken first gave a proof by finding and verifying 1936 reducible unavoidable sets, and a simplified proof of Robertson, Sanders, Seymour and Thomas in 1997 only involved 633 reducible unavoidable sets, both proofs could not be realized effectively by hand. Until now, finding the reducible unavoidable sets remains the only successful method to use, which came from Kempe's first "proof" of the four color problem in 1879. An alternative method only involving 4 reducible unavoidable sets for proving the four color theorem is used in this paper, which takes form of mathematical proof rather than a computer-assisted proof and proves both the four color conjecture and the uniquely 4-colorable planar graph conjecture by mathematical method.

Citations

• Every planar map is four colorable. Part I: Discharging
• Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
• The size of uniquely colorable graphs
• On Hamiltonian Circuits
• An introduction to chromatic polynomials
• The Solution of the Four-Color-Map Problem
• Cubic graphs with three Hamiltonian cycles are not always uniquely edge colorable
• Every planar map is four colorable
• The Reducibility of Maps
• On the Geographical Problem of the Four Colours
• The Four Color Problem

Cited by

• Theory on Structure and Coloring of Maximal Planar Graphs (I): Relationship between Structure and Coloring

Discussions

• Four color problem finally proved without a computer? [hn, 1 points, 2 comments]

Related

• A formal proof of the four color theorem
• A Simple Proof for the Four-Color Theorem
• A Simple Proof of the Four-Color Theorem
• To Prove Four Color Theorem
• The Four Color Theorem -- A New Simple Proof by Induction