Every Planar Map Is Four Colorable
By K. Appel, W. Haken. Mathematical Solitaires & Games, 2019
645 citations recorded by the source corpus.
As has become standard, the four color map problem will be considered in the dual sense as the problem of whether the vertices of every planar graph (without loops) can be colored with at most four colors in such a way that no pair of vertices which lie on a common edge have the same color. The restriction to triangulations with all vertices of degree at least five is a consequence of the work of A. B. Kempe. Over the past 100 years, a number of authors including A. B. Kempe, G. D. Birkhoff, and H. Heesch have developed a theory of reducibility to attack the problem. Simultaneously, a theory of unavoidable sets has been developed and the fusion of these has led to the proof. A configuration is a subgraph of a planar triangulation consisting of a circuit (called the ring) and its interior. A configuration is called reducible if it can be shown by certain standard methods that it cannot be immersed in a minimal counterexample to the four color conjecture. (For details, see [3] or [4].) A set of configurations is called unavoidable if every planar triangulation contains some member of the set. From the definitions, it is immediate that the four color theorem is proved if an unavoidable set of reducible configurations is provided. The most efficient known method of producing unavoidable sets of configurations is called the method of discharging. This method treats the planar triangulation as an electrical network with charge assigned to the vertices. Euler's formula is used to show that the initial charge distribution, giving positive charge to vertices of degree five and negative charge to vertices of degree greater than six, has positive total charge. Next, the initial charge is redistributed in a manner which obeys the principle of conservation of charge. This means that some vertices must end up with positive charge. Such an algorithm can be made sufficiently sophisticated that a finite list of neighborhoods of all possible vertices of ultimately positive charge can be described in detail.
Subfields: Computational Theory and Mathematics, Computer Graphics and Computer-Aided Design
View Paper: https://www.semanticscholar.org/paper/bc56c92f130ac41f672f0320bfb9291dbbef54dd
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Theory and Mathematics
In Computer Graphics and Computer-Aided Design
Citations in the corpus
- Defective and Clustered Graph Colouring (2018, background): “The 4-colour theorem [19, 196] says that every planar graph is properly 4-colourable.”
- Discrete mathematics (2004, neutral): “Exclusive or: p ⊕ q is true when exactly one of p and q is true, and false otherwise Truth table: Instructor:I¸sılDillig, CS311H:DiscreteMathematics Introand PropositionalLogic 25/36”
- Tait colorings, and an instanton homology for webs and foams (2015, positive): “The existence of Tait colorings for bridgeless trivalent graphs in the plane is equivalent to the four-color theorem (see [22]), so the above conjecture would provide an alternative proof of the theorem of Appel and Haken [1]: every planar graph admits a four-coloring.”