|
An unavoidable set of  -reducible configurations
Author(s):
John
P.
Steinberger
Journal:
Trans. Amer. Math. Soc.
362
(2010),
6633-6661.
MSC (2000):
Primary 05C15
Posted:
July 9, 2010
MathSciNet review:
2678989
Retrieve article in:
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  -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:
-
- 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, http://research.microsoft. com/
 gonthier/fourcolor.pdf. - 11.
- W. Haken, Shimamoto's construction, manuscript (1971), available at http://www.math. ubc. ca/
 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/
 thomas/OLDFTP/four. - 17.
- -, Discharging cartwheels, available at http://math.gatech.edu/
 thomas/ OLDFTP/four. - 18.
- W.R. Stromquist, Some aspects of the four color problem, Ph.D., Harvard University, 1975. Available at http:// www.walterstromquist.com.
- 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
Email:
jpsteinb@gmail.com
DOI:
10.1090/S0002-9947-2010-05092-5
PII:
S 0002-9947(2010)05092-5
Keywords:
Graph theory,
four-color theorem
Received by editor(s):
July 7, 2008
Received by editor(s) in revised form:
April 23, 2009
Posted:
July 9, 2010
Copyright of article:
Copyright
2010,
American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.
|
