Four-colour problem

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 ()? 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