Normal tree orders for infinite graphs

Authors:
J.-M. Brochet and R. Diestel

Journal:
Trans. Amer. Math. Soc. **345** (1994), 871-895

MSC:
Primary 05C05

MathSciNet review:
1260198

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 to trees of arbitrary height. Applications include a structure theorem for graphs without large complete topological minors. A number of open problems are suggested.

**[1]**J. M. Brochet,*Covers of graphs by infinite generalized paths*, submitted.**[2]**-,*Paths and trees in graphs with no infinite independent set*, submitted.**[3]**-,*Tree partitions of infinite graphs into fully connected subgraphs*, submitted.**[4]**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**, 10.1016/0012-365X(91)90328-Y**[5]**J. M. Brochet and R. Diestel,*Normal tree orders in infinite graphs*II, in preparation.**[6]**Reinhard Diestel,*The structure of 𝑇𝐾ₐ-free graphs*, J. Combin. Theory Ser. B**54**(1992), no. 2, 222–238. MR**1152450**, 10.1016/0095-8956(92)90054-2**[7]**-,*The end structure of a graph*, Discrete Math.**95**(1991), 69-89.**[8]**Reinhard Diestel and Imre Leader,*A proof of the bounded graph conjecture*, Invent. Math.**108**(1992), no. 1, 131–162. MR**1156388**, 10.1007/BF02100602**[9]**R. Diestel,*The classification of finitely spreading graphs*, submitted.**[10]**-,*The depth-first search tree structure of*-*free graphs*, J. Combin. Theory B**60**(1994).**[11]**R. Halin,*Simplicial decompositions of infinite graphs*, Ann. Discrete Math.**3**(1978), 93–109. Advances in graph theory (Cambridge Combinatorial Conf., Trinity Coll., Cambridge, 1977). MR**499113****[12]**H. A. Jung,*Zusammenzüge und Unterteilungen von Graphen*, Math. Nachr.**35**(1967), 241–267 (German). MR**0228366****[13]**H. A. Jung,*Wurzelbäume und unendliche Wege in Graphen*, Math. Nachr.**41**(1969), 1–22 (German). MR**0266807****[14]**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.

Retrieve articles in *Transactions of the American Mathematical Society*
with MSC:
05C05

Retrieve articles in all journals with MSC: 05C05

Additional Information

DOI:
https://doi.org/10.1090/S0002-9947-1994-1260198-4

Article copyright:
© Copyright 1994
American Mathematical Society