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

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

MathSciNet review:
1260198

Full-text PDF

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), 23-47. MR**1141930 (93f:05065)****[5]**J. M. Brochet and R. Diestel,*Normal tree orders in infinite graphs*II, in preparation.**[6]**R. Diestel,*The structure of*-*free graphs*, J. Combin. Theory B**54**(1992), 222-238. MR**1152450 (93a:05103)****[7]**-,*The end structure of a graph*, Discrete Math.**95**(1991), 69-89.**[8]**R. Diestel and I. Leader,*A proof of the bounded graph conjecture*, Invent. Math.**108**(1992), 131-162. MR**1156388 (93f:05095)****[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*, Advances in Graph Theory (Annals of Discrete Mathematics, vol. 3 (B. Bollobás, ed.), North-Holland, Amsterdam and London, 1978. MR**499113 (80a:05162)****[12]**H. A. Jung,*Zusammenzüge und Unterteilungen von Graphen*, Math. Nachr.**35**(1967), 241-268. MR**0228366 (37:3947)****[13]**-,*Wurzelbäume und unendliche Wege in Graphen*, Math. Nachr.**41**(1969), 1-22. MR**0266807 (42:1710)****[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