Bulletin of the American Mathematical Society

Author(s): László Lovász
Journal: Bull. Amer. Math. Soc. 43 (2006), 75-86.
MSC (2000): Primary 05C83
Posted: October 24, 2005
Retrieve article in: PDF DVI PostScript

Abstract: A monumental project in graph theory was recently completed. The project, started by Robertson and Seymour, and later joined by Thomas, led to entirely new concepts and a new way of looking at graph theory.

The motivating problem was Kuratowski's characterization of planar graphs, and a far-reaching generalization of this, conjectured by Wagner: If a class of graphs is minor-closed (i.e., it is closed under deleting and contracting edges), then it can be characterized by a finite number of excluded minors. The proof of this conjecture is based on a very general theorem about the structure of large graphs: If a minor-closed class of graphs does not contain all graphs, then every graph in it is glued together in a tree-like fashion from graphs that can almost be embedded in a fixed surface.

We describe the precise formulation of the main results and survey some of its applications to algorithmic and structural problems in graph theory.

1.: D. Archdeacon and P. Huneke: A Kuratowski theorem for nonorientable surfaces, J. Combin. Theory Ser. B 46 (1989), 173-231. MR 0992991 (90f:05049)
2.: S. Arnborg and A. Proskurowski: Linear time algorithms for NP-hard problems restricted to partial k-trees, Discrete Appl. Math. 23 (1989), 11-24. MR 0985145 (90a:05156)
3.: L. Babai: Authomorphism groups of graphs and edge contraction, Discrete Math. 8 (1974), 13-22. MR 0332554 (48:10881)
4.: B. Bollobás and A. Thomason: Highly linked graphs, Combinatorica 16 (1996), 313-320. MR 1417341 (97h:05104)
5.: G. Chen, R.J. Gould, K. Kawarabayashi, F. Pfender and B. Wei: Graph Minors and Linkages (preprint).
6.: M. Chudnovsky, N. Robertson, P.D. Seymour and R. Thomas: The Strong Perfect Graph Theorem (to appear).
7.: M. Conforti, G. Cornuejols and M.R. Rao: Decomposition of balanced matrices, J. Combin. Theory Ser. B 77 (1999), 292-406. MR 1719340 (2001d:05126)
8.: M. Conforti, G. Cornuejols, A. Kapoor and K. Vuskovic: Balanced 0,+1,-1 matrices, Part I: Decomposition. J. Combin. Theory Ser. B 81 (2001), 243-274. MR 1814907 (2002c:05041)
9.: G.A. Dirac: A property of 4-chromatic graphs and some remarks on critical graphs J. London Math. Soc. 27 (1952), 85-92. MR 0045371 (13:572f)
10.: J.B. Kruskal: Well-quasi-ordering, the Tree Theorem, and Vazsonyi's conjecture, Trans. of the Amer. Math. Soc. 95 (1960), 210-225. MR 0111704 (22:2566)
11.: J.B. Kruskal: The theory of well-quasi-ordering: A frequently discovered concept, J. Combinatorial Theory Ser. A 13 (1972), 297-305. MR 0306057 (46:5184)
12.: K. Kuratowski: Sur le probleme des courbes gauches en topologie, Fund. Math.16 (1930), 271-283.
13.: B. Mohar: A linear time algorithm for embedding graphs in an arbitrary surface, SIAM J. Discrete Math. 12 (1999), 6-26. MR 1666045 (2000a:05068)
14.: B. Mohar: Graph minors and graphs on surfaces, in: Surveys in Combinatorics, Proc. 18th British Comb. Conf. (ed. J.W.P. Hirschfeld), London Math. Soc. Lecture Note Ser. 288 (2001), Cambridge Univ. Press, 145-163. MR 1850707 (2002g:05173)
15.: C. St.J. A. Nash-Williams: On well-quasi-ordering finite trees, Proc. of the Cambridge Phil. Soc. 59 (1963) 833-835. MR 0153601 (27:3564)
16.: N. Robertson, P.D. Seymour: Graph minors III. Planar tree-width, J. Combin. Theory Ser. B 36 (1984), 49-64. MR 0742386 (86f:05103)
17.: N. Robertson, P.D. Seymour: Graph minors IV. Tree-width and well-quasi-ordering, J. Combin. Theory Ser. B 48 (1990), 227-254. MR 1046757 (91g:05039)
18.: N. Robertson, P.D. Seymour: Graph minors V. Excluding a planar graph, J. Combin. Theory Ser. B 41 (1986), 92-114. MR 0854606 (89m:05070)
19.: N. Robertson, P.D. Seymour: Graph minors VIII. A Kuratowski theorem for general surfaces, J. Combin. Theory Ser. B 48 (1990), 255-288. MR 1046758 (91g:05040)
20.: N. Robertson, P.D. Seymour: Graph minors IX. Disjoint crossed paths, J. Combin. Theory Ser. B 49 (1990), 40-77. MR 1056819 (91g:05041)
21.: N. Robertson, P.D. Seymour: Graph minors X. Obstructions to tree-decomposition, J. Combin. Theory Ser. B 52 (1991), 153-190. MR 1110468 (92g:05158)
22.: N. Robertson, P.D. Seymour: Graph minors XIII. The disjoint paths problem, J. Combin. Theory Ser. B 63 (1995), 65-110. MR 1309358 (97b:05088)
23.: N. Robertson, P.D. Seymour: Graph minors XVI. Excluding a non-planar graph, J. Combin. Theory Ser. B 89 (2003), 43-76. MR 1999736 (2004f:05168)
24.: N. Robertson, P.D. Seymour: Graph minors XVII. Taming a vortex, J. Combin. Theory Ser. B 77 (1999), 162-210. MR 1710538 (2001f:05128)
25.: N. Robertson, P.D. Seymour: Graph minors XVIII. Tree-decompositions and well-quasi-ordering, J. Combin. Theory Ser. B 89 (2003), 77-108. MR 1999737 (2005e:05116)
26.: N. Robertson, P.D. Seymour: Graph minors XIX. Well-quasi-ordering on a surface, J. Combin. Theory Ser. B 90 (2004), 325-385. MR 2034033 (2005b:05204)
27.: N. Robertson, P.D. Seymour: Graph minors XX. Wagner's Conjecture J. Combin. Theory Ser. B (to appear).
28.: N. Robertson, P.D. Seymour and R. Thomas: Sach's linkless embedding conjecture, Journal of Comb. Theory Series B, 64 (1995), 185-227. MR 1339849 (96m:05072)
29.: P. Seymour: Disjoint paths in graphs, Discrete Math. 29 (1980), 293-309. MR 0560773 (82b:05091)
30.: P. Seymour: Decomposition of regular matroids, Journal of Comb. Theory Series B, 28 (1980), 305-359. MR 0579077 (82j:05046)
31.: S. Tarkowski: On the comparability of dendrites, Bull. Acad. Polon. Sci. Math. Astronom. Phys. 8 (1960), 39-41. MR 0123491 (23:A816)
32.: C. Thomassen: 2-linked graphs, Europ. J. Combin. 1 (1980), 371-378. MR 0595938 (82c:05086)
33.: W.T. Tutte: Lectures on Matroids, J. Res. Nat. Bur. Standards 69B (1965), 1-47. MR 0179781 (31:4023)
34.: K. Wagner: Über eine Eigenschaft der ebenen Komplexe, Mathematische Annalen 114 (1937), 570-590.
35.: K. Wagner: Über eine Erweiterung des Satzes von Kuratowski, Deutsche Mathematik 2 (1937), 280-285.
36.: K. Wagner: Graphentheorie, B.J. Hochschultaschenbucher 248/248a, Mannheim (1970), 61. MR 0282850 (44:84)

Retrieve articles in Bulletin of the American Mathematical Society with MSC (2000): 05C83

László Lovász
Affiliation: Microsoft Research, Redmond, Washington 98052

DOI: 10.1090/S0273-0979-05-01088-8
PII: S 0273-0979(05)01088-8
Received by editor(s): June 6, 2005,
Received by editor(s) in revised form: August 9, 2005
Posted: October 24, 2005
Additional Notes: This article is based on a lecture presented January 7, 2005, at the AMS Special Session on Current Events, Joint Mathematics Meetings, Atlanta, GA.
Copyright of article: Copyright 2005, American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-9485(e) ISSN 0273-0979(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues: 1891 - Present Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS