A unified existence theorem for normal spanning trees
From MaRDI portal
Publication:2200933
DOI10.1016/J.JCTB.2020.07.002zbMATH Open1448.05037arXiv2003.11575OpenAlexW3045616271MaRDI QIDQ2200933FDOQ2200933
Authors: Max F. Pitz 
Publication date: 24 September 2020
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Abstract: We show that a graph has a normal spanning tree if and only if its vertex set is the union of countably many sets each separated from any subdivided infinite clique in by a finite set of vertices. This proves a conjecture by Brochet and Diestel from 1994, giving a common strengthening of two classical normal spanning tree criterions due to Jung and Halin. Moreover, our method gives a new, algorithmic proof of Halin's theorem that every connected graph not containing a subdivision of a countable clique has a normal spanning tree.
Full work available at URL: https://arxiv.org/abs/2003.11575
Recommendations
Cites Work
- A proof of the bounded graph conjecture
- Simplicial Decompositions of Infinite Graphs
- Wurzelbäume und unendliche Wege in Graphen
- Graph Theory
- The Classification of Finitely Spreading Graphs
- Ends and multi-endings. II
- The depth-first search tree structure of \(TK_{\aleph_ 0}\)-free graphs
- Excluding Subdivisions of Infinite Cliques
- Normal Tree Orders for Infinite Graphs
Cited In (6)
- Quickly proving Diestel's normal spanning tree criterion
- Expanders Are Universal for the Class of All Spanning Trees
- Proof of Halin's normal spanning tree conjecture
- Applications of Order Trees in Infinite Graphs
- Duality theorems for stars and combs III: Undominated combs
- A new obstruction for normal spanning trees
This page was built for publication: A unified existence theorem for normal spanning trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2200933)
