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

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. 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
  • 2. K. Appel and W. Haken, Every planar map is four colorable. I. Discharging, Illinois J. Math. 21 (1977), no. 3, 429–490. MR 0543792
  • 3. K. Appel, W. Haken, and J. Koch, Every planar map is four colorable. II. Reducibility, Illinois J. Math. 21 (1977), no. 3, 491–567. MR 0543793
  • 4. 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
  • 5. G.D. Birkhoff, The reducibility of maps, Amer. J. Math. 70 (1913), 114-128.
  • 6. Arthur Bernhart, Another reducible edge configuration, Amer. J. Math. 70 (1948), 144–146. MR 0023513,
  • 7. D.I.A. Cohen, Block-count reducibility and the four-color theorem, manuscript.
  • 8. Rudolf Fritsch and Gerda Fritsch, The four-color theorem, Springer-Verlag, New York, 1998. History, topological foundations, and idea of proof; Translated from the 1994 German original by Julie Peschke. MR 1633950
  • 9. 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
  • 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. Heinrich Heesch, Untersuchungen zum Vierfarbenproblem, B. I. Hochschulskripten, vol. 810/810, Bibliographisches Institut, Mannheim-Vienna-Zürich, 1969 (German). MR 0248048
  • 13. A. B. Kempe, On the Geographical Problem of the Four Colours, Amer. J. Math. 2 (1879), no. 3, 193–200. MR 1505218,
  • 14. 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
  • 15. Neil Robertson, Daniel Sanders, Paul Seymour, and Robin Thomas, The four-colour theorem, J. Combin. Theory Ser. B 70 (1997), no. 1, 2–44. MR 1441258,
  • 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. 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

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