Remote Access 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
DOI: https://doi.org/10.1090/S1079-6762-96-00003-0
MathSciNet review: 1405965
Full-text PDF

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. 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. MR 80m:05031
  • 2. 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. MR 80i:05041
  • 3. K. Appel and W. Haken, Every planar map is four colorable. Part I. Discharging, Illinois J. Math. 21 (1977), 429--490. MR 58:27598d
  • 4. K. Appel, W. Haken, and J. Koch, Every planar map is four colorable. Part II. Reducibility, Illinois J. Math 21 (1977), 491--567. MR 58:27598d
  • 5. K. Appel and W. Haken, Every planar map is four colorable, A.M.S. Contemporary Math. 98 (1989). MR 91m:05079
  • 6. A. Bernhart, Another reducible edge configuration, Amer. J. Math. 70 (1948), 144--146. MR 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, Congr. Numer. 82 (1991), 33--48. MR 92j:05069
  • 11. H. Heesch, Untersuchungen zum Vierfarbenproblem, Hochschulskriptum 810/a/b, Bibliographisches Institüt, Mannheim, 1969. MR 40:1303
  • 12. A. B. Kempe, On the geographical problem of the four colors, Amer. J. Math. 2 (1879), 193--200.
  • 13. 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. MR 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. 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. MR 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: https://doi.org/10.1090/S1079-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

American Mathematical Society