A proof of the bounded graph conjecture (Q1207424): Difference between revisions

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.