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 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 $ \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), 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 $ {\text{T}}{K_{{\aleph _0}}}$-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.

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