A proof of the bounded graph conjecture
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.
- A short proof of the restricted Ramsey theorem for finite set systems
- Bounded graphs
- scientific article; zbMATH DE number 4095512 (Why is no real title available?)
- scientific article; zbMATH DE number 48089 (Why is no real title available?)
- On spanning trees and k-connectedness in infinite graphs
- Simplicial Decompositions of Infinite Graphs
- Universal graphs and universal functions
- Wurzelbäume und unendliche Wege in Graphen
- Bounded graphs
- The end structure of a graph: Recent results and open problems
- Proof of the Seymour conjecture for large graphs
- Domination games on infinite graphs
- Topological paths, cycles and spanning trees in infinite graphs
- A unified existence theorem for normal spanning trees
- A simple existence criterion for normal spanning trees
- Cardinal characteristics on graphs
- The Growth of Infinite Graphs: Boundedness and Finite Spreading
- Normal Tree Orders for Infinite Graphs
- A proof of Cunningham's conjecture on restricted subgraphs and jump systems
- scientific article; zbMATH DE number 2094795 (Why is no real title available?)
- A conjecture concerning a limit of non-Cayley graphs
- The fundamental group of a locally finite graph with ends
- The homology of a locally finite graph with ends
- End spaces and spanning trees
- A short proof of a theorem on degree sets of graphs
This page was built for publication: A proof of the bounded graph conjecture
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1207424)
