Namespaces
Variants
Actions

Difference between revisions of "Four-colour problem"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(TeX)
 
Line 1: Line 1:
 +
{{TEX|done}}
 
Can the regions of an arbitrary planar map (cf. [[Graph, planar|Graph, planar]]) be coloured by four colours in such a way that any two adjacent regions are coloured with different colours?
 
Can the regions of an arbitrary planar map (cf. [[Graph, planar|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|Graph colouring]]) of any planar graph does not exceed <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040970/f0409701.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040970/f0409702.png" />)? The numerous attempts to solve the four-colour problem have influenced the development of certain branches of [[Graph theory|graph theory]]. In 1976 an affirmative answer to the four-colour problem, with the use of a computer, was announced (cf. ).
+
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|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|graph theory]]. In 1976 an affirmative answer to the four-colour problem, with the use of a computer, was announced (cf. ).
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  F. Harary,  "Graph theory" , Addison-Wesley  (1969)  pp. Chapt. 9</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  O. Ore,  "The four-colour problem" , Acad. Press  (1967)</TD></TR><TR><TD valign="top">[3a]</TD> <TD valign="top">  K. Appel,  W. Haken,  "Every map is four-colorable I. Discharging"  ''Illinois J. Math.'' , '''21''' :  3  (1977)  pp. 429–490</TD></TR><TR><TD valign="top">[3b]</TD> <TD valign="top">  K. Appel,  W. Haken,  "Every map is four-colorable II. Reducibility"  ''Illinois J. Math.'' , '''21''' :  3  (1977)  pp. 491–567</TD></TR></table>
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  F. Harary,  "Graph theory" , Addison-Wesley  (1969)  pp. Chapt. 9</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  O. Ore,  "The four-colour problem" , Acad. Press  (1967)</TD></TR><TR><TD valign="top">[3a]</TD> <TD valign="top">  K. Appel,  W. Haken,  "Every map is four-colorable I. Discharging"  ''Illinois J. Math.'' , '''21''' :  3  (1977)  pp. 429–490</TD></TR><TR><TD valign="top">[3b]</TD> <TD valign="top">  K. Appel,  W. Haken,  "Every map is four-colorable II. Reducibility"  ''Illinois J. Math.'' , '''21''' :  3  (1977)  pp. 491–567</TD></TR></table>

Latest revision as of 19:20, 17 April 2014

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=16340
This article was adapted from an original article by V.B. Alekseev (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article