Normal tree orders for infinite graphs
Authors:
J.M. Brochet and R. Diestel
Journal:
Trans. Amer. Math. Soc. 345 (1994), 871895
MSC:
Primary 05C05
MathSciNet review:
1260198
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: A wellfounded 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, GallaiMilgram properties for infinite graphs,
Discrete Math. 95 (1991), no. 13, 23–47.
Directions in infinite graph theory and combinatorics (Cambridge, 1989). MR 1141930
(93f:05065), http://dx.doi.org/10.1016/0012365X(91)90328Y
 [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
(93a:05103), http://dx.doi.org/10.1016/00958956(92)900542
 [7]
, The end structure of a graph, Discrete Math. 95 (1991), 6989.
 [8]
Reinhard
Diestel and Imre
Leader, A proof of the bounded graph conjecture, Invent. Math.
108 (1992), no. 1, 131–162. MR 1156388
(93f:05095), http://dx.doi.org/10.1007/BF02100602
 [9]
R. Diestel, The classification of finitely spreading graphs, submitted.
 [10]
, The depthfirst 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
(80a:05162)
 [12]
H.
A. Jung, Zusammenzüge und Unterteilungen von Graphen,
Math. Nachr. 35 (1967), 241–267 (German). MR 0228366
(37 #3947)
 [13]
H.
A. Jung, Wurzelbäume und unendliche Wege in Graphen,
Math. Nachr. 41 (1969), 1–22 (German). 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.), NorthHolland, Amsterdam, 1992.
 [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, GallaiMilgram properties for infinite graphs, Discrete Math. 95 (1991), 2347. 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), 222238. MR 1152450 (93a:05103)
 [7]
 , The end structure of a graph, Discrete Math. 95 (1991), 6989.
 [8]
 R. Diestel and I. Leader, A proof of the bounded graph conjecture, Invent. Math. 108 (1992), 131162. MR 1156388 (93f:05095)
 [9]
 R. Diestel, The classification of finitely spreading graphs, submitted.
 [10]
 , The depthfirst 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.), NorthHolland, Amsterdam and London, 1978. MR 499113 (80a:05162)
 [12]
 H. A. Jung, Zusammenzüge und Unterteilungen von Graphen, Math. Nachr. 35 (1967), 241268. MR 0228366 (37:3947)
 [13]
 , Wurzelbäume und unendliche Wege in Graphen, Math. Nachr. 41 (1969), 122. 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.), NorthHolland, 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
DOI:
http://dx.doi.org/10.1090/S00029947199412601984
PII:
S 00029947(1994)12601984
Article copyright:
© Copyright 1994
American Mathematical Society
