Excluding infinite trees
HTML articles powered by AMS MathViewer
- by P. D. Seymour and Robin Thomas PDF
- Trans. Amer. Math. Soc. 335 (1993), 597-630 Request permission
Abstract:
For each infinite cardinal $\kappa$ we give several necessary and sufficient conditions for a graph not to contain a minor isomorphic to the infinite $\kappa$-branching tree in terms of a certain kind of a "tree-decomposition," in terms of a "path-decomposition," and also in terms of a "cops-and-robber game." We also give necessary and sufficient conditions for a graph not to contain a subgraph isomorphic to a subdivision of the same tree.References
- Dan Bienstock, Neil Robertson, Paul Seymour, and Robin Thomas, Quickly excluding a forest, J. Combin. Theory Ser. B 52 (1991), no. 2, 274–283. MR 1110475, DOI 10.1016/0095-8956(91)90068-U
- R. Halin, Charakterisierung der Graphen ohne unendliche Wege, Arch. Math. 16 (1965), 227–231 (German). MR 179104, DOI 10.1007/BF01220026
- R. Halin, Über unendliche Wege in Graphen, Math. Ann. 157 (1964), 125–137 (German). MR 170340, DOI 10.1007/BF01362670
- Richard Laver, Better-quasi-orderings and a class of trees, Studies in foundations and combinatorics, Adv. in Math. Suppl. Stud., vol. 1, Academic Press, New York-London, 1978, pp. 31–48. MR 520553
- Neil Robertson and P. D. Seymour, Graph minors. I. Excluding a forest, J. Combin. Theory Ser. B 35 (1983), no. 1, 39–61. MR 723569, DOI 10.1016/0095-8956(83)90079-5 N. Robertson, P. D. Seymour, and R. Thomas, Excluding infinite clique minors (submitted).
- Paul Seymour and Robin Thomas, An end-faithful spanning tree counterexample, Proc. Amer. Math. Soc. 113 (1991), no. 4, 1163–1171. MR 1045600, DOI 10.1090/S0002-9939-1991-1045600-8 —, Graph searching, and a minimax theorem for tree-width, J. Combin. Theory Ser. B (to appear).
Additional Information
- © Copyright 1993 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 335 (1993), 597-630
- MSC: Primary 05C75; Secondary 03E05, 03E35, 05C05
- DOI: https://doi.org/10.1090/S0002-9947-1993-1079058-6
- MathSciNet review: 1079058