A new proof of the four-colour theorem
Authors:
Neil Robertson, Daniel P. Sanders, Paul Seymour and Robin Thomas
Journal:
Electron. Res. Announc. Amer. Math. Soc. 2 (1996), 17-25
MSC (1991):
Primary 05C10, 05C15, 05C85
DOI:
https://doi.org/10.1090/S1079-6762-96-00003-0
MathSciNet review:
1405965
Full-text PDF Free Access
Abstract |
References |
Similar Articles |
Additional Information
Abstract: The four-colour theorem, that every loopless planar graph admits a vertex-colouring with at most four different colours, was proved in 1976 by Appel and Haken, using a computer. Here we announce another proof, still using a computer, but simpler than Appel and Haken’s in several respects.
- Frank Allaire, Another proof of the four colour theorem. I, Proceedings of the Seventh Manitoba Conference on Numerical Mathematics and Computing (Univ. Manitoba, Winnipeg, Man., 1977) Congress. Numer., XX, Utilitas Math., Winnipeg, Man., 1978, pp. 3–72. MR 535003
- Frank Allaire and Edward Reinier Swart, A systematic approach to the determination of reducible configurations in the four-color conjecture, J. Combin. Theory Ser. B 25 (1978), no. 3, 339–362. MR 516267, DOI https://doi.org/10.1016/0095-8956%2878%2990010-2
- K. Appel and W. Haken, Every planar map is four colorable. I. Discharging, Illinois J. Math. 21 (1977), no. 3, 429–490. MR 543792
- K. Appel and W. Haken, Every planar map is four colorable. I. Discharging, Illinois J. Math. 21 (1977), no. 3, 429–490. MR 543792
- Kenneth Appel and Wolfgang Haken, Every planar map is four colorable, Contemporary Mathematics, vol. 98, American Mathematical Society, Providence, RI, 1989. With the collaboration of J. Koch. MR 1025335
- A. Bernhart, Another reducible edge configuration, Amer. J. Math. 70 (1948), 144–146.
- G. D. Birkhoff, The reducibility of maps, Amer. J. Math. 35 (1913), 114–128.
- D. I. A. Cohen, Block count consistency and the four color problem, manuscript.
- K. Dürre, H. Heesch, and F. Miehe, Eine Figurenliste zur chromatischen Reduktion, manuscript eingereicht am 15.8.1977.
- S. J. Gismondi and E. R. Swart, A new type of $4$-colour reducibility, Proceedings of the Twenty-second Southeastern Conference on Combinatorics, Graph Theory, and Computing (Baton Rouge, LA, 1991), 1991, pp. 33–48. MR 1152056
- Heinrich Heesch, Untersuchungen zum Vierfarbenproblem, B. I. Hochschulskripten, vol. 810/810, Bibliographisches Institut, Mannheim-Vienna-Zürich, 1969 (German). MR 0248048
- A. B. Kempe, On the geographical problem of the four colors, Amer. J. Math. 2 (1879), 193–200.
- Jean Mayer, Une propriété des graphes minimaux dans le problème des quatre couleurs, Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976) Colloq. Internat. CNRS, vol. 260, CNRS, Paris, 1978, pp. 291–295 (French, with English summary). MR 539995
- N. Robertson, D. P. Sanders, P. D. Seymour, and R. Thomas, The four colour theorem, manuscript.
- ---, Reducibility in the four colour theorem, unpublished manuscript available from ftp://ftp.math.gatech.edu/pub/users/thomas/four.
- ---, Discharging cartwheels, unpublished manuscript available from ftp://ftp.math.gatech.edu/pub/users/thomas/four.
- P. G. Tait, Note on a theorem in geometry of position, Trans. Roy. Soc. Edinburgh 29 (1880), 657–660.
- Hassler Whitney and W. T. Tutte, Kempe chains and the four colour problem, Studies in graph theory, Part II, Math. Assoc. Amer., Washington, D.C., 1975, pp. 378–413. Studies in Math., Vol. 12. MR 0392651
- F. Allaire, Another proof of the four colour theorem-Part I, Proc. of the 7th Manitoba Conf. on Numerical Math. and Computing (1977), Congressus Numerantium XX, Utilitas Math., Winnipeg, 1978, pp. 3–72.
- F. Allaire and E. R. Swart, A systematic approach to the determination of reducible configurations in the four-color conjecture, J. Combinatorial Theory, Ser. B 25 (1978), 339–362.
- K. Appel and W. Haken, Every planar map is four colorable. Part I. Discharging, Illinois J. Math. 21 (1977), 429–490.
- K. Appel, W. Haken, and J. Koch, Every planar map is four colorable. Part II. Reducibility, Illinois J. Math 21 (1977), 491–567.
- K. Appel and W. Haken, Every planar map is four colorable, A.M.S. Contemporary Math. 98 (1989).
- A. Bernhart, Another reducible edge configuration, Amer. J. Math. 70 (1948), 144–146.
- G. D. Birkhoff, The reducibility of maps, Amer. J. Math. 35 (1913), 114–128.
- D. I. A. Cohen, Block count consistency and the four color problem, manuscript.
- K. Dürre, H. Heesch, and F. Miehe, Eine Figurenliste zur chromatischen Reduktion, manuscript eingereicht am 15.8.1977.
- S. J. Gismondi and E. R. Swart, A new type of 4-colour reducibility, Congr. Numer. 82 (1991), 33–48.
- H. Heesch, Untersuchungen zum Vierfarbenproblem, Hochschulskriptum 810/a/b, Bibliographisches Institüt, Mannheim, 1969.
- A. B. Kempe, On the geographical problem of the four colors, Amer. J. Math. 2 (1879), 193–200.
- J. Mayer, Une propriété des graphes minimaux dans le problème des quatre couleurs, Problèmes Combinatoires et Théorie des Graphes, Colloques internationaux CNRS No. 260, Paris, 1978.
- N. Robertson, D. P. Sanders, P. D. Seymour, and R. Thomas, The four colour theorem, manuscript.
- ---, Reducibility in the four colour theorem, unpublished manuscript available from ftp://ftp.math.gatech.edu/pub/users/thomas/four.
- ---, Discharging cartwheels, unpublished manuscript available from ftp://ftp.math.gatech.edu/pub/users/thomas/four.
- P. G. Tait, Note on a theorem in geometry of position, Trans. Roy. Soc. Edinburgh 29 (1880), 657–660.
- H. Whitney and W. T. Tutte, Kempe chains and the four colour problem, Studies in Graph Theory (D. R. Fulkerson, eds.), Part II, Math. Assoc. of America, 1975, pp. 378–413.
Similar Articles
Retrieve articles in Electronic Research Announcements of the American Mathematical Society
with MSC (1991):
05C10,
05C15,
05C85
Retrieve articles in all journals
with MSC (1991):
05C10,
05C15,
05C85
Additional Information
Neil Robertson
Affiliation:
Department of Mathematics, Ohio State University, 231 W. 18th Ave., Columbus, Ohio 43210, USA
Email:
robertso@math.ohio-state.edu
Daniel P. Sanders
Affiliation:
School of Mathematics, Georgia Institute of Technology, Atlanta, Georgia 30332, USA
Email:
dsanders@math.ohio-state.edu
Paul Seymour
Affiliation:
Bellcore, 445 South Street, Morristown, New Jersey 07960, USA
Email:
pds@bellcore.com
Robin Thomas
Affiliation:
School of Mathematics, Georgia Institute of Technology, Atlanta, Georgia 30332, USA
MR Author ID:
217850
Email:
thomas@math.gatech.edu
Received by editor(s):
September 26, 1995
Additional Notes:
Research partially performed under a consulting agreement with Bellcore, and partially supported by DIMACS Center, Rutgers University, New Brunswick, New Jersey 08903, USA.
Neil Robertson was partially supported by NSF under Grant No. DMS-8903132 and by ONR under Grant No. N00014-92-J-1965.
Daniel P. Sanders was partially supported by DIMACS and by ONR under Grant No. N00014-93-1-0325.
Robin Thomas was partially supported by NSF under Grant No. DMS-9303761 and by ONR under Grant No. N00014-93-1-0325.
Communicated by:
Ronald Graham
Article copyright:
© Copyright 1996
N. Robertson, D. P. Sanders, P. Seymour, R. Thomas
