A proof of the bounded graph conjecture. (English) Zbl 0793.05121

Given a ray \(R: v_ 1 v_ 2\dots\) in the graph \(G\) and a function \(f: V(G)\to\mathbb{N}\), the sequence \(\sigma: V(G)\to\mathbb{N}\) is said to dominate \(f\) on \(R\), if \(\sigma(n)\geq f(v_ n)\) for all but finitely many \(n\in\mathbb{N}\). The graph \(G\) is called bounded if for each \(f: V(G)\to\mathbb{N}\) some sequence \(\sigma\) dominates \(f\) on every ray in \(G\). The authors characterize the bounded countable graphs as those not containing a subdivision of any of three particular countable graphs as subgraphs. This characterization was conjectured by Halin in 1964. General bounded graphs \(G\) are characterized by the additional property that \(G\) must not contain \(\kappa\) disjoint rays, where \(\kappa\) is a certain cardinal such that \(\omega<\kappa\leq 2^ \omega\) (\(\kappa= \omega_ 1\) if \(2^ \omega= \omega_ 1\)). Also the exclusion of the three (four) basic graphs as minors characterizes the countable (general) bounded graphs.
Reviewer: H.A.Jung (Berlin)


05C99 Graph theory
05C10 Planar graphs; geometric and topological aspects of graph theory
05C75 Structural characterization of families of graphs
Full Text: DOI EuDML


[1] Diestel, R.: Graph Decompositions-a study in infinite graph theory. Oxford: Oxford University Press 1990 · Zbl 0726.05001
[2] Diestel, R.: On spanning trees andk-connectedness in infinite graphs J. Comb. Theory, Ser. B (to appear) · Zbl 0780.05013
[3] Halin, R.: Simplicial decompositions of infinite graphs. In: Bollobás, B. (ed.) Advances in Graph Theory (Ann. Discrete Math., vol. 3) Amsterdam London: North-Holland 1978 · Zbl 0383.05034
[4] Halin, R.: Some problems and results in infinite graphs In: Andersen L.D. et al. (eds.) Graph Theory in Memory of G.A. Dirac. (Ann. Discrete Math., vol. 41) Amsterdam London: North-Holland 1989 · Zbl 0669.05052
[5] Halin, R.: Bounded graphs. In: Diestel, R. (ed.) Directions in infinite graph theory and combinatorics Discrete Math.95 (1991) · Zbl 0770.05093
[6] Jung, H.A.: Wurzelbäume und unendliche Wege in Graphen. Math. Nachr.41, 1–22 (1969) · Zbl 0177.27001
[7] König, D.: Theorie der endlichen und unendlichen Graphen. Leipzig: 1936 Akademische Verlagsgesellschaft; reprinted: New York: Chelsea 1950 · JFM 62.0654.05
[8] Prömel, H.J., Voigt, B.: Aspects of Ramsey Theory. Berlin Heidelberg New York: Springer (in preparation) · Zbl 0695.05051
[9] Rado, R.: Universal graphs and universal functions. Acta Arith.,9, 331–340 (1964) · Zbl 0139.17303
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.