## Graph minor theory

HTML articles powered by AMS MathViewer

- by László Lovász PDF
- Bull. Amer. Math. Soc.
**43**(2006), 75-86 Request permission

## 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.

## References

- Dan Archdeacon and Phil Huneke,
*A Kuratowski theorem for nonorientable surfaces*, J. Combin. Theory Ser. B**46**(1989), no. 2, 173–231. MR**992991**, DOI 10.1016/0095-8956(89)90043-9 - Stefan Arnborg and Andrzej Proskurowski,
*Linear time algorithms for NP-hard problems restricted to partial $k$-trees*, Discrete Appl. Math.**23**(1989), no. 1, 11–24. MR**985145**, DOI 10.1016/0166-218X(89)90031-0 - László Babai,
*Automorphism groups of graphs and edge-contraction*, Discrete Math.**8**(1974), 13–20. MR**332554**, DOI 10.1016/0012-365X(74)90104-6 - Béla Bollobás and Andrew Thomason,
*Highly linked graphs*, Combinatorica**16**(1996), no. 3, 313–320. MR**1417341**, DOI 10.1007/BF01261316
CGKPW G. Chen, R.J. Gould, K. Kawarabayashi, F. Pfender and B. Wei: Graph Minors and Linkages (preprint).
CRST M. Chudnovsky, N. Robertson, P.D. Seymour and R. Thomas: The Strong Perfect Graph Theorem (to appear).
- Michele Conforti, Gérard Cornuéjols, and M. R. Rao,
*Decomposition of balanced matrices*, J. Combin. Theory Ser. B**77**(1999), no. 2, 292–406. MR**1719340**, DOI 10.1006/jctb.1999.1932 - Michele Conforti, Gérard Cornuéjols, Ajai Kapoor, and Kristina Vu ković,
*Balanced $0,\pm 1$ matrices. I. Decomposition*, J. Combin. Theory Ser. B**81**(2001), no. 2, 243–274. MR**1814907**, DOI 10.1006/jctb.2000.2010 - G. A. Dirac,
*A property of $4$-chromatic graphs and some remarks on critical graphs*, J. London Math. Soc.**27**(1952), 85–92. MR**45371**, DOI 10.1112/jlms/s1-27.1.85 - J. B. Kruskal,
*Well-quasi-ordering, the Tree Theorem, and Vazsonyi’s conjecture*, Trans. Amer. Math. Soc.**95**(1960), 210–225. MR**111704**, DOI 10.1090/S0002-9947-1960-0111704-1 - Joseph B. Kruskal,
*The theory of well-quasi-ordering: A frequently discovered concept*, J. Combinatorial Theory Ser. A**13**(1972), 297–305. MR**306057**, DOI 10.1016/0097-3165(72)90063-5
Kur K. Kuratowski: Sur le probleme des courbes gauches en topologie, - Bojan Mohar,
*A linear time algorithm for embedding graphs in an arbitrary surface*, SIAM J. Discrete Math.**12**(1999), no. 1, 6–26. MR**1666045**, DOI 10.1137/S089548019529248X - Bojan Mohar,
*Graph minors and graphs on surfaces*, Surveys in combinatorics, 2001 (Sussex), London Math. Soc. Lecture Note Ser., vol. 288, Cambridge Univ. Press, Cambridge, 2001, pp. 145–163. MR**1850707** - C. St. J. A. Nash-Williams,
*On well-quasi-ordering finite trees*, Proc. Cambridge Philos. Soc.**59**(1963), 833–835. MR**153601**, DOI 10.1017/s0305004100003844 - Neil Robertson and P. D. Seymour,
*Graph minors. III. Planar tree-width*, J. Combin. Theory Ser. B**36**(1984), no. 1, 49–64. MR**742386**, DOI 10.1016/0095-8956(84)90013-3 - Neil Robertson and P. D. Seymour,
*Graph minors. IV. Tree-width and well-quasi-ordering*, J. Combin. Theory Ser. B**48**(1990), no. 2, 227–254. MR**1046757**, DOI 10.1016/0095-8956(90)90120-O - Neil Robertson and P. D. Seymour,
*Graph minors. V. Excluding a planar graph*, J. Combin. Theory Ser. B**41**(1986), no. 1, 92–114. MR**854606**, DOI 10.1016/0095-8956(86)90030-4 - Neil Robertson and P. D. Seymour,
*Graph minors. VIII. A Kuratowski theorem for general surfaces*, J. Combin. Theory Ser. B**48**(1990), no. 2, 255–288. MR**1046758**, DOI 10.1016/0095-8956(90)90121-F - Neil Robertson and P. D. Seymour,
*Graph minors. IX. Disjoint crossed paths*, J. Combin. Theory Ser. B**49**(1990), no. 1, 40–77. MR**1056819**, DOI 10.1016/0095-8956(90)90063-6 - Neil Robertson and P. D. Seymour,
*Graph minors. X. Obstructions to tree-decomposition*, J. Combin. Theory Ser. B**52**(1991), no. 2, 153–190. MR**1110468**, DOI 10.1016/0095-8956(91)90061-N - Neil Robertson and P. D. Seymour,
*Graph minors. XIII. The disjoint paths problem*, J. Combin. Theory Ser. B**63**(1995), no. 1, 65–110. MR**1309358**, DOI 10.1006/jctb.1995.1006 - Neil Robertson and P. D. Seymour,
*Graph minors. XVI. Excluding a non-planar graph*, J. Combin. Theory Ser. B**89**(2003), no. 1, 43–76. MR**1999736**, DOI 10.1016/S0095-8956(03)00042-X - Neil Robertson and P. D. Seymour,
*Graph minors. XVII. Taming a vortex*, J. Combin. Theory Ser. B**77**(1999), no. 1, 162–210. MR**1710538**, DOI 10.1006/jctb.1999.1919 - Neil Robertson and Paul Seymour,
*Graph minors. XVIII. Tree-decompositions and well-quasi-ordering*, J. Combin. Theory Ser. B**89**(2003), no. 1, 77–108. MR**1999737**, DOI 10.1016/S0095-8956(03)00067-4 - Neil Robertson and P. D. Seymour,
*Graph minors. XIX. Well-quasi-ordering on a surface*, J. Combin. Theory Ser. B**90**(2004), no. 2, 325–385. MR**2034033**, DOI 10.1016/j.jctb.2003.08.005
RS20 N. Robertson, P.D. Seymour: Graph minors XX. Wagner’s Conjecture - Neil Robertson, Paul Seymour, and Robin Thomas,
*Sachs’ linkless embedding conjecture*, J. Combin. Theory Ser. B**64**(1995), no. 2, 185–227. MR**1339849**, DOI 10.1006/jctb.1995.1032 - P. D. Seymour,
*Disjoint paths in graphs*, Discrete Math.**29**(1980), no. 3, 293–309. MR**560773**, DOI 10.1016/0012-365X(80)90158-2 - P. D. Seymour,
*Decomposition of regular matroids*, J. Combin. Theory Ser. B**28**(1980), no. 3, 305–359. MR**579077**, DOI 10.1016/0095-8956(80)90075-1 - S. Tarkowski,
*On the comparability of dendrites*, Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys.**8**(1960), 39–41 (English, with Russian summary). MR**123491** - Carsten Thomassen,
*$2$-linked graphs*, European J. Combin.**1**(1980), no. 4, 371–378. MR**595938**, DOI 10.1016/S0195-6698(80)80039-4 - W. T. Tutte,
*Lectures on matroids*, J. Res. Nat. Bur. Standards Sect. B**69B**(1965), 1–47. MR**179781**, DOI 10.6028/jres.069B.001
Wag1 K. Wagner: Über eine Eigenschaft der ebenen Komplexe, - Klaus Wagner,
*Graphentheorie*, B. I. Hochschultaschenbücher, Band 248/248a*, Bibliographisches Institut, Mannheim-Vienna-Zürich, 1970 (German). MR**0282850**

*Fund. Math.*

**16**(1930), 271–283.

*J. Combin. Theory*Ser. B (to appear).

*Mathematische Annalen*

**114**(1937), 570–590. Wag2 K. Wagner: Über eine Erweiterung des Satzes von Kuratowski,

*Deutsche Mathematik*

**2**(1937), 280–285.

## Additional Information

**László Lovász**- Affiliation: Microsoft Research, Redmond, Washington 98052
- Received by editor(s): June 6, 2005
- Received by editor(s) in revised form: August 9, 2005
- Published electronically: 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 2005
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication. - Journal: Bull. Amer. Math. Soc.
**43**(2006), 75-86 - MSC (2000): Primary 05C83
- DOI: https://doi.org/10.1090/S0273-0979-05-01088-8
- MathSciNet review: 2188176