Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Electronic Research Announcements
Electronic Research Announcements
ISSN 1079-6762

   

 

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
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.


References [Enhancements On Off] (What's this?)

  • 1. 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 (80m:05031)
  • 2. 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 (80i:05041), http://dx.doi.org/10.1016/0095-8956(78)90010-2
  • 3. K. Appel and W. Haken, Supplement to: “Every planar map is four colorable. I. Discharging”\ (Illinois J. Math. 21 (1977), no. 3, 429–490) by Appel and Haken; “II. Reducibility” (ibid. 21 (1977), no. 3, 491–567) by Appel, Haken and J. Koch, Illinois J. Math. 21 (1977), no. 3, 1–251. (microfiche supplement). MR 0543795 (58 #27598d)
  • 4. K. Appel and W. Haken, Supplement to: “Every planar map is four colorable. I. Discharging”\ (Illinois J. Math. 21 (1977), no. 3, 429–490) by Appel and Haken; “II. Reducibility” (ibid. 21 (1977), no. 3, 491–567) by Appel, Haken and J. Koch, Illinois J. Math. 21 (1977), no. 3, 1–251. (microfiche supplement). MR 0543795 (58 #27598d)
  • 5. 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 (91m:05079)
  • 6. Arthur Bernhart, Another reducible edge configuration, Amer. J. Math. 70 (1948), 144–146. MR 0023513 (9,366g)
  • 7. G. D. Birkhoff, The reducibility of maps, Amer. J. Math. 35 (1913), 114--128.
  • 8. D. I. A. Cohen, Block count consistency and the four color problem, manuscript.
  • 9. K. Dürre, H. Heesch, and F. Miehe, Eine Figurenliste zur chromatischen Reduktion, manuscript eingereicht am 15.8.1977.
  • 10. 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 (92j:05069)
  • 11. Heinrich Heesch, Untersuchungen zum Vierfarbenproblem, B. I. Hochschulskripten, vol. 810/810, Bibliographisches Institut, Mannheim-Vienna-Zürich, 1969 (German). MR 0248048 (40 #1303)
  • 12. A. B. Kempe, On the geographical problem of the four colors, Amer. J. Math. 2 (1879), 193--200.
  • 13. 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 (80m:05042)
  • 14. N. Robertson, D. P. Sanders, P. D. Seymour, and R. Thomas, The four colour theorem, manuscript.
  • 15. ------, Reducibility in the four colour theorem, unpublished manuscript available from
    ftp://ftp.math.gatech.edu/pub/users/thomas/four.
  • 16. ------, Discharging cartwheels, unpublished manuscript available from
    ftp://ftp.math.gatech.edu/pub/users/thomas/four.
  • 17. P. G. Tait, Note on a theorem in geometry of position, Trans. Roy. Soc. Edinburgh 29 (1880), 657--660.
  • 18. 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 (52 #13468)

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
Email: thomas@math.gatech.edu

DOI: http://dx.doi.org/10.1090/S1079-6762-96-00003-0
PII: S 1079-6762(96)00003-0
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