Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



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

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 $ \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 [Enhancements On Off] (What's this?)

  • [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 $ {\text{T}}{K_a}$-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 $ {\text{T}}{K_{{\aleph _0}}}$-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.

Similar Articles

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

Retrieve articles in all journals with MSC: 05C05

Additional Information

Article copyright: © Copyright 1994 American Mathematical Society

American Mathematical Society