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, Fund. Math.16 (1930), 271–283.
- 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 J. Combin. Theory Ser. B (to appear).
- 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, Mathematische Annalen 114 (1937), 570–590. Wag2 K. Wagner: Über eine Erweiterung des Satzes von Kuratowski, Deutsche Mathematik 2 (1937), 280–285.
- Klaus Wagner, Graphentheorie, B. I. Hochschultaschenbücher, Band 248/248a*, Bibliographisches Institut, Mannheim-Vienna-Zürich, 1970 (German). MR 0282850
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