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

endend spaceinfinite graphnormal spanning treeparacompact

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

• 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.
• scientific article; zbMATH DE number 42114 (Why is no real title available?)
• 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

(10)

• A tree-of-tangles theorem for infinite tangles
• Countably determined ends and graphs
• Gomory‐Hu trees of infinite graphs with finite total weight
• End spaces and tree-decompositions
• Connectoids. I: A universal end space theory
• Edge-connectivity between edge-ends of infinite graphs
• A metrization theorem for edge-end spaces of infinite graphs
• A representation theorem for end spaces of infinite graphs
• End spaces and spanning trees
• 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)