Normal tree orders for infinite graphs
HTML articles powered by AMS MathViewer
- by J.-M. Brochet and R. Diestel PDF
- Trans. Amer. Math. Soc. 345 (1994), 871-895 Request permission
Abstract:
A well-founded tree T denned on the vertex set of a graph G is called normal if the endvertices of any edge of G are comparable in T. We study how normal trees can be used to describe the structure of infinite graphs. In particular, we extend Jung’s classical existence theorem for trees of height $\omega$ to trees of arbitrary height. Applications include a structure theorem for graphs without large complete topological minors. A number of open problems are suggested.References
-
J. M. Brochet, Covers of graphs by infinite generalized paths, submitted.
—, Paths and trees in graphs with no infinite independent set, submitted.
—, Tree partitions of infinite graphs into fully connected subgraphs, submitted.
- J.-M. Brochet and M. Pouzet, Gallai-Milgram properties for infinite graphs, Discrete Math. 95 (1991), no. 1-3, 23–47. Directions in infinite graph theory and combinatorics (Cambridge, 1989). MR 1141930, DOI 10.1016/0012-365X(91)90328-Y J. M. Brochet and R. Diestel, Normal tree orders in infinite graphs II, in preparation.
- Reinhard Diestel, The structure of $TK_a$-free graphs, J. Combin. Theory Ser. B 54 (1992), no. 2, 222–238. MR 1152450, DOI 10.1016/0095-8956(92)90054-2 —, The end structure of a graph, Discrete Math. 95 (1991), 69-89.
- Reinhard Diestel and Imre Leader, A proof of the bounded graph conjecture, Invent. Math. 108 (1992), no. 1, 131–162. MR 1156388, DOI 10.1007/BF02100602 R. Diestel, The classification of finitely spreading graphs, submitted. —, The depth-first search tree structure of ${\text {T}}{K_{{\aleph _0}}}$-free graphs, J. Combin. Theory B 60 (1994).
- R. Halin, Simplicial decompositions of infinite graphs, Ann. Discrete Math. 3 (1978), 93–109. MR 499113
- H. A. Jung, Zusammenzüge und Unterteilungen von Graphen, Math. Nachr. 35 (1967), 241–267 (German). MR 228366, DOI 10.1002/mana.19670350503
- H. A. Jung, Wurzelbäume und unendliche Wege in Graphen, Math. Nachr. 41 (1969), 1–22 (German). MR 266807, DOI 10.1002/mana.19690410102 N. Robertson, P. D Seymour, and R. Thomas, Excluding infinite minors, Directions in Infinite Graph Theory and Combinatorics, Topics in Discrete Mathematics, vol. 3 (R. Diestel, ed.), North-Holland, Amsterdam, 1992.
Additional Information
- © Copyright 1994 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 345 (1994), 871-895
- MSC: Primary 05C05
- DOI: https://doi.org/10.1090/S0002-9947-1994-1260198-4
- MathSciNet review: 1260198