×

The four-colour theorem. (English) Zbl 0883.05056

The four-colour theorem, that every loopless planar graph has a vertex colouring with at most four colours, was proved by Appel and Haken in 1976, using a computer. Here another proof is given, still using a computer, but simpler than the original.

MSC:

05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Allaire, F., Another proof of the four colour theorem—Part I, Congr. Numer., 20, 3-72 (1977)
[2] Allaire, F.; Swart, E. R., A systematic approach to the determination of reducible configurations in the four-color conjecture, J. Combin. Theory Ser. B, 25, 339-362 (1978) · Zbl 0398.05034
[3] Appel, K.; Haken, W., Every Planar Map Is Four Colorable. Every Planar Map Is Four Colorable, A.M.S. Contemp. Math., 98 (1989) · Zbl 0681.05027
[4] Appel, K.; Haken, W., Every planar map is four colorable. Part I. Discharging, Illinois J. Math., 21, 429-490 (1977) · Zbl 0387.05009
[5] Appel, K.; Haken, W.; Koch, J., Every planar map is four colorable. Part II. Reducibility, Illinois J. Math., 21, 491-567 (1977) · Zbl 0387.05010
[6] Bernhart, A., Another reducible edge configuration, Amer. J. Math., 70, 144-146 (1948) · Zbl 0034.40102
[7] Birkhoff, G. D., The reducibility of maps, Amer. J. Math., 35, 114-128 (1913) · JFM 44.0568.01
[8] D. I. A. Cohen, Block count consistency and the four color problem; D. I. A. Cohen, Block count consistency and the four color problem
[9] K. Dürre, H. Heesch, F. Miehe, 1977, Eine Figurenliste zur chromatischen Reduktion; K. Dürre, H. Heesch, F. Miehe, 1977, Eine Figurenliste zur chromatischen Reduktion
[10] Gismondi, S. J.; Swart, E. R., A new type of 4-colour reducibility, Proceedings, 22 nd Southeastern Conf. on Combinatorics, Graph Theory, and Computing. Proceedings, 22 nd Southeastern Conf. on Combinatorics, Graph Theory, and Computing, Congr. Numer., 82 (1991), p. 33-48 · Zbl 0764.05026
[11] H. Heesch, 1969, Untersuchungen zum Vierfarbenproblem, Bibliographisches Institut, Mannheim; H. Heesch, 1969, Untersuchungen zum Vierfarbenproblem, Bibliographisches Institut, Mannheim
[12] Kempe, A. B., On the geographical problem of the four colours, Amer. J. Math., 2, 183-200 (1879)
[13] Mayer, J., Une propriété des graphes minimaux dans le problème des quatre couleurs, Colloques internationaux C.N.R.S., No. 260, pp. 291-295 (1978) · Zbl 0419.05022
[14] Tait, P. G., Note on a theorem in geometry of position, Trans. Roy. Soc. Edinburgh, 29, 657-660 (1880) · JFM 12.0409.01
[15] Whitney, H.; Tutte, W. T., Kempe chains and the four colour problem, Studies in Graph Theory, Part II. Studies in Graph Theory, Part II, Math. Assoc. of America (1975) · Zbl 0328.05107
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.