Excluding infinite trees

Seymour, P. D.; Thomas, Robin

doi:10.1090/S0002-9947-1993-1079058-6

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

Excluding infinite clique minors

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