Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



An unavoidable set of $ D$-reducible configurations

Author: John P. Steinberger
Journal: Trans. Amer. Math. Soc. 362 (2010), 6633-6661
MSC (2000): Primary 05C15
Published electronically: July 9, 2010
MathSciNet review: 2678989
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We give a new proof of the four-color theorem by exhibiting an unavoidable set of 2822 $ D$-reducible configurations. The existence of such a set had been conjectured by several researchers including Stromquist (1975), Appel and Haken (1977), and Robertson, Sanders, Seymour and Thomas (1997).

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

  • 1. F. Allaire, Another proof of the four colour theorem. I, Proc. of the 7th Manitoba Conf. on Numerical Math. and Computing (1977), Congressius Numerantum XX, Utilitas Math., Winnipeg, 1978, 3-72. MR 535003 (80m:05031)
  • 2. K. Appel and W. Haken, Every planar map is four-colorable. I. Discharging, Illinois Journal of Mathematics 21 (1977), 429-490. MR 0543792 (58:27598a)
  • 3. K. Appel, W. Haken and J. Koch, Every planar map is four-colorable. II. Reducibility, Illinois Journal of Mathematics 21 (1977), 491-567. MR 0543793 (58:27598b)
  • 4. K. Appel and W. Haken, Every planar map is four colorable, A.M.S. Contemporary Math. 98 (1989). MR 1025335 (91m:05079)
  • 5. G.D. Birkhoff, The reducibility of maps, Amer. J. Math. 70 (1913), 114-128.
  • 6. A. Bernhart, Another reducible edge configuration, Amer. J. Math. 35 (1948), 144-146. MR 0023513 (9:366g)
  • 7. D.I.A. Cohen, Block-count reducibility and the four-color theorem, manuscript.
  • 8. R. Fritsch and G. Fritsch, The four-color theorem, Springer-Verlag (1998). MR 1633950 (99i:05079)
  • 9. S.J. Gismondi and E.R. Swart, A new type of four-colour reducibility, Congr. Numer. 82 (1991), 33-48. MR 1152056 (92j:05069)
  • 10. G. Gonthier, A computer-checked proof of the four-color theorem, com/$ \sim$gonthier/fourcolor.pdf.
  • 11. W. Haken, Shimamoto's construction, manuscript (1971), available at http://www.math. ubc. ca/$ \sim$jpsteinb/index.html.
  • 12. H. Heesch, Untersuchungen zum Vierfarbenproblem, Hochschulskriptum 810/a/b, Bibliographisches Institüt, Mannheim, 1969. MR 0248048 (40:1303)
  • 13. A. B. Kempe, On the geographical problem of the four colors, Amer. J. Math. 2 (1879), 193-200. MR 1505218
  • 14. J. Mayer, Une propriété des graphes minimaux dans le problème des quatres couleurs, Problèmes Combinatoires et Théorie des Graphes, Colloques internationaux CNRS No. 260, Paris, 1978. MR 539995 (80m:05042)
  • 15. N. Robertson, D.P. Sanders, P.D. Seymour and R. Thomas, The four-colour theorem, J. Combin. Theorey Ser. B 70, (1997), 2-42. MR 1441258 (98c:05065)
  • 16. -, Reducibility in the four colour theorem, available at http://math.gatech. edu/$ \sim$thomas/OLDFTP/four.
  • 17. -, Discharging cartwheels, available at$ \sim$thomas/ OLDFTP/four.
  • 18. W.R. Stromquist, Some aspects of the four color problem, Ph.D., Harvard University, 1975. Available at http://
  • 19. 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 0392651 (52:13468)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 05C15

Retrieve articles in all journals with MSC (2000): 05C15

Additional Information

John P. Steinberger
Affiliation: Department of Mathematics, University of British Columbia, 1984 Mathematics Road, Vancouver, British Columbia, Canada V6T 1Z2
Address at time of publication: Department of Mathematics, FIT Building 1-208, Tsinghua University, Beijing, 100084, People’s Republic of China

Keywords: Graph theory, four-color theorem
Received by editor(s): July 7, 2008
Received by editor(s) in revised form: April 23, 2009
Published electronically: July 9, 2010
Article copyright: © Copyright 2010 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society