A unified existence theorem for normal spanning trees

DOI10.1016/J.JCTB.2020.07.002MaRDI QIDQ2200933zbMATHOpenAlexFDO

Authors Max F. Pitz

Publication date 24 September 2020

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2003.11575

zbMATH Keywords

normal spanning tree

Mathematics Subject Classification ID

Trees (05C05)

Abstract: We show that a graph $G$ 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 $G$ 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.

Recommendations

• A simple existence criterion for normal spanning trees
• Proof of Halin's normal spanning tree conjecture
• Normal Spanning Trees, Aronszajn Trees and Excluded Minors
• A new obstruction for normal spanning trees
• Quickly proving Diestel's normal spanning tree criterion

Cites work

• A proof of the bounded graph conjecture
• Ends and multi-endings. II
• Excluding Subdivisions of Infinite Cliques
• Graph theory
• Normal Tree Orders for Infinite Graphs
• Simplicial Decompositions of Infinite Graphs
• The Classification of Finitely Spreading Graphs
• The depth-first search tree structure of \(TK_{\aleph_ 0}\)-free graphs
• Wurzelbäume und unendliche Wege in Graphen

Cited in

(9)

• Duality theorems for stars and combs III: Undominated combs
• Applications of Order Trees in Infinite Graphs
• A simple existence criterion for normal spanning trees
• Quickly proving Diestel's normal spanning tree criterion
• A new obstruction for normal spanning trees
• Minimal obstructions for normal spanning trees
• Proof of Halin's normal spanning tree conjecture
• Expanders Are Universal for the Class of All Spanning Trees
• Approximating infinite graphs by normal 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)