Approximating infinite graphs by normal trees

DOI10.1016/J.JCTB.2020.12.007MaRDI QIDQ1998763zbMATH OpenOpenAlexFDO

Authors Jan Kurkofka, Ruben Melcher, Max F. Pitz

Publication date 8 March 2021

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

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

zbMATH Keywords

infinite graphnormal spanning treeparacompactendend space

Mathematics Subject Classification ID

Trees (05C05) Infinite graphs (05C63)

Abstract: We show that every connected graph can be approximated by a normal tree, up to some arbitrarily small error phrased in terms of neighbourhoods around its ends. The existence of such approximate normal trees has consequences of both combinatorial and topological nature. On the combinatorial side, we show that a graph has a normal spanning tree as soon as it has normal spanning trees locally at each end; i.e., the only obstruction for a graph to having a normal spanning tree is an end for which none of its neighbourhoods has a normal spanning tree. On the topological side, we show that the end space $Omega(G)$, as well as the spaces $|G|=GcupOmega(G)$ naturally associated with a graph $G$, are always paracompact. This gives unified and short proofs for a number of results by Diestel, Spr"ussel and Polat, and answers an open question about metrizability of end spaces by Polat.

Recommendations

• End spaces and spanning trees
• End spaces of graphs are normal
• A unified existence theorem for normal spanning trees
• Ends and multi-endings. I
• A simple existence criterion for normal spanning trees

Cites work

• scientific article; zbMATH DE number 42114 (Why is no real title available?)
• End spaces and spanning trees
• End spaces of graphs are normal
• Ends and multi-endings. I
• Ends and multi-endings. II
• Graph-theoretical versus topological ends of graphs.
• Minimal obstructions for normal spanning trees
• Normal Spanning Trees, Aronszajn Trees and Excluded Minors
• The end structure of a graph: Recent results and open problems
• Trees and ultrametric spaces: A categorical equivalence
• Une généralisation des espaces compacts
• Wurzelbäume und unendliche Wege in Graphen

Cited in

(6)

• A tree-of-tangles theorem for infinite tangles
• End spaces and tree-decompositions
• End spaces and spanning trees
• Countably determined ends and graphs
• Gomory‐Hu trees of infinite graphs with finite total weight
• End spaces of graphs are normal

This page was built for publication: Approximating infinite graphs by normal trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1998763)