Namespaces
Variants
Actions

Four-colour problem

From Encyclopedia of Mathematics
Revision as of 19:20, 17 April 2014 by Ivan (talk | contribs) (TeX)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Can the regions of an arbitrary planar map (cf. Graph, planar) be coloured by four colours in such a way that any two adjacent regions are coloured with different colours?

The conjecture that the answer to the four-colour problem is affirmative was formulated in the 19th century. In 1890 a weaker assertion was proved, namely that every planar map can be coloured with five colours. Replacing any planar map by its dual planar graph, one obtains an equivalent formulation of the four-colour problem in terms of graphs: Is it true that the chromatic number (cf. Graph colouring) of any planar graph does not exceed $4$ ($\chi(G)\leq4$)? The numerous attempts to solve the four-colour problem have influenced the development of certain branches of graph theory. In 1976 an affirmative answer to the four-colour problem, with the use of a computer, was announced (cf. ).

References

[1] F. Harary, "Graph theory" , Addison-Wesley (1969) pp. Chapt. 9
[2] O. Ore, "The four-colour problem" , Acad. Press (1967)
[3a] K. Appel, W. Haken, "Every map is four-colorable I. Discharging" Illinois J. Math. , 21 : 3 (1977) pp. 429–490
[3b] K. Appel, W. Haken, "Every map is four-colorable II. Reducibility" Illinois J. Math. , 21 : 3 (1977) pp. 491–567
How to Cite This Entry:
Four-colour problem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Four-colour_problem&oldid=31833
This article was adapted from an original article by V.B. Alekseev (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article