|
|
|
|
four-color conjecture
|
(Theorem)
|
|
|
The four-color conjecture was a long-standing problem posed by Francis Guthrie to his professor Augustus De Morgan in 1852, while coloring a map of England. The conjecture states that every map on a plane or a sphere can be colored using only four colors such that no two adjacent countries are assigned the same color. There are maps that need four colors to be colored as the figure below shows. This conjecture equivalent to
the statement that chromatic number of every planar graph is no more than four.
Figure: Four mutually adjacent countries
| 1#1 |
After many unsuccessful attempts the conjecture was proven by Appel and Haken in 1976 with the aid of a computer. Before it was known that every planar map can be five-colored by the work of Heawood in 1890.
Interestingly, the seemingly harder problem of determining the maximal number of colors needed for all surfaces other than the sphere was solved long before the four-color conjecture was settled. This is the Heawood number of the surface unless the surface is the Klein bottle in which case it is $6$ .
- 1
- Kenneth O. May.
The origin of the four-color conjecture.
Isis, 56(3):346-348, 1965.
Available online at JSTOR.
- 2
- Thomas L. Saaty and Paul C. Kainen.
The Four-Color Problem: Assaults and Conquest.
Dover, 1986.
Zbl 0463.05041.
|
"four-color conjecture" is owned by bbukh. [ full author list (2) ]
|
|
(view preamble | get metadata)
Cross-references: Klein bottle, Heawood number, surfaces, maximal number, computer, planar graph, chromatic number, adjacent, colors, sphere, plane, conjecture, coloring
There are 4 references to this entry.
This is version 16 of four-color conjecture, born on 2003-01-04, modified 2006-08-02.
Object id is 3875, canonical name is FourColorConjecture.
Accessed 13136 times total.
Classification:
| AMS MSC: | 05C15 (Combinatorics :: Graph theory :: Coloring of graphs and hypergraphs) | | | 05C10 (Combinatorics :: Graph theory :: Topological graph theory, imbedding) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|
