|
|
|
Viewing Version
4
of
'four-color conjecture'
|
[ view 'four-color conjecture'
|
back to history
]
| Title of object: |
four-color conjecture |
| Canonical Name: |
FourColorConjecture |
| Type: |
Theorem |
| Created on: |
2003-01-04 21:52:15 |
| Modified on: |
2003-02-07 23:40:36 |
| Classification: |
msc:05C15, msc:05C10 |
| Synonyms: |
four-color conjecture=Appel-Haken theorem
four-color conjecture=4-color conjecture |
Revision comment (for changes between this and next version):
Preamble:
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
\renewcommand{\bibname}{References} |
Content:
The four-color conjecture was a long-standing problem posed by Guthrie 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. This is equivalent to the statement that chromatic number of every planar graph is no more than four. After many unsuccessfull attempts the conjecture was proven by Appel and Haken in 1976 with an aid of computer.
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 number is now called the Heawood number of the surface.
\begin{thebibliography}{1}
\bibitem{cite:saaty_kainen_fcc}
Thomas~L. Saaty and Paul~C. Kainen.
\newblock {\em The Four-Color Problem: Assaults and Conquest}.
\newblock Dover, 1986.
\end{thebibliography}
%@BOOK{cite:saaty_kainen_fcc,
% author = {Thomas L. Saaty and Paul C. Kainen},
% title = {The Four-Color Problem: Assaults and Conquest},
% publisher = {Dover},
% year = 1986
%} |
|
|
|
|
|
