|
A new proof of the four-colour theorem
Author(s):
Neil
Robertson;
Daniel
P.
Sanders;
Paul
Seymour;
Robin
Thomas
Journal:
Electron. Res. Announc. Amer. Math. Soc.
2
(1996),
17-25.
MSC (1991):
Primary 05C10, 05C15, 05C85
Retrieve article in:
PDF DVI PostScript
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:
- 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
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
Email:
robertso@math.ohio-state.edu
Daniel
P.
Sanders
Affiliation:
School of Mathematics, Georgia Institute of Technology, Atlanta, Georgia 30332
Email:
dsanders@math.ohio-state.edu
Paul
Seymour
Affiliation:
Bellcore, 445 South Street, Morristown, New Jersey 07960
Email:
pds@bellcore.com
Robin
Thomas
Affiliation:
School of Mathematics, Georgia Institute of Technology, Atlanta, Georgia 30332, USA
Email:
thomas@math.gatech.edu
DOI:
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.
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
Copyright of article:
Copyright
1996,
N. Robertson, D. P. Sanders, P. Seymour, R. Thomas
|
Comments: webmaster@ams.org