Graph minor theory

Lovász, László

doi:10.1090/S0273-0979-05-01088-8

			Journals Home Search Author Info Subscribe Tech Support My Subscriptions Browser Compatibility Info Help
ISSN 1088-9485(online) ISSN 0273-0979(print)

Graph minor theory

Author: László Lovász
Journal: Bull. Amer. Math. Soc. 43 (2006), 75-86
MSC (2000): Primary 05C83
Posted: October 24, 2005
MathSciNet review: 2188176
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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. Dan Archdeacon and Phil Huneke, A Kuratowski theorem for nonorientable surfaces, J. Combin. Theory Ser. B 46 (1989), no. 2, 173–231. MR 992991 (90f:05049), http://dx.doi.org/10.1016/0095-8956(89)90043-9
2. Stefan Arnborg and Andrzej Proskurowski, Linear time algorithms for NP-hard problems restricted to partial 𝑘-trees, Discrete Appl. Math. 23 (1989), no. 1, 11–24. MR 985145 (90a:05156), http://dx.doi.org/10.1016/0166-218X(89)90031-0
3. László Babai, Automorphism groups of graphs and edge-contraction, Discrete Math. 8 (1974), 13–20. MR 0332554 (48 #10881)
4. Béla Bollobás and Andrew Thomason, Highly linked graphs, Combinatorica 16 (1996), no. 3, 313–320. MR 1417341 (97h:05104), http://dx.doi.org/10.1007/BF01261316
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. 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 (2001d:05126), http://dx.doi.org/10.1006/jctb.1999.1932
8. Michele Conforti, Gérard Cornuéjols, Ajai Kapoor, and Kristina Vušković, Balanced 0,±1 matrices. I. Decomposition, J. Combin. Theory Ser. B 81 (2001), no. 2, 243–274. MR 1814907 (2002c:05041), http://dx.doi.org/10.1006/jctb.2000.2010
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. Amer. Math. Soc. 95 (1960), 210–225. MR 0111704 (22 #2566), http://dx.doi.org/10.1090/S0002-9947-1960-0111704-1
11. Joseph 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. Bojan Mohar, A linear time algorithm for embedding graphs in an arbitrary surface, SIAM J. Discrete Math. 12 (1999), no. 1, 6–26 (electronic). MR 1666045 (2000a:05068), http://dx.doi.org/10.1137/S089548019529248X
14. 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 (2002g:05173)
15. C. St. J. A. Nash-Williams, On well-quasi-ordering finite trees, Proc. Cambridge Philos. Soc. 59 (1963), 833–835. MR 0153601 (27 #3564)
16. 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 (86f:05103), http://dx.doi.org/10.1016/0095-8956(84)90013-3
17. 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 (91g:05039), http://dx.doi.org/10.1016/0095-8956(90)90120-O
18. 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 (89m:05070), http://dx.doi.org/10.1016/0095-8956(86)90030-4
19. 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 (91g:05040), http://dx.doi.org/10.1016/0095-8956(90)90121-F
20. 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 (91g:05041), http://dx.doi.org/10.1016/0095-8956(90)90063-6
21. 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 (92g:05158), http://dx.doi.org/10.1016/0095-8956(91)90061-N
22. 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 (97b:05088), http://dx.doi.org/10.1006/jctb.1995.1006
23. 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 (2004f:05168), http://dx.doi.org/10.1016/S0095-8956(03)00042-X
24. 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 (2001f:05128), http://dx.doi.org/10.1006/jctb.1999.1919
25. 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 (2005e:05116), http://dx.doi.org/10.1016/S0095-8956(03)00067-4
26. 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 (2005b:05204), http://dx.doi.org/10.1016/j.jctb.2003.08.005
27. N. Robertson, P.D. Seymour: Graph minors XX. Wagner's Conjecture J. Combin. Theory Ser. B (to appear).
28. Neil Robertson, Paul Seymour, and Robin Thomas, Sachs’ linkless embedding conjecture, J. Combin. Theory Ser. B 64 (1995), no. 2, 185–227. MR 1339849 (96m:05072), http://dx.doi.org/10.1006/jctb.1995.1032
29. P. D. Seymour, Disjoint paths in graphs, Discrete Math. 29 (1980), no. 3, 293–309. MR 560773 (82b:05091), http://dx.doi.org/10.1016/0012-365X(80)90158-2
30. P. D. Seymour, Decomposition of regular matroids, J. Combin. Theory Ser. B 28 (1980), no. 3, 305–359. MR 579077 (82j:05046), http://dx.doi.org/10.1016/0095-8956(80)90075-1
31. 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 0123491 (23 #A816)
32. Carsten Thomassen, 2-linked graphs, European J. Combin. 1 (1980), no. 4, 371–378. MR 595938 (82c:05086)
33. W. T. Tutte, Lectures on matroids, J. Res. Nat. Bur. Standards Sect. B 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. Klaus Wagner, Graphentheorie, B.I-Hochschultaschenbücher, vol. 248/248, Bibliographisches Institut, Mannheim, 1970 (German). MR 0282850 (44 #84)

	Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
\|