Approximating infinite graphs by normal trees

DOI10.1016/J.JCTB.2020.12.007zbMATH Open1459.05220arXiv2002.08340OpenAlexW3120385352MaRDI QIDQ1998763FDOQ1998763

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)

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.

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

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

zbMATH Keywords

infinite graphnormal spanning treeparacompactendend space

Mathematics Subject Classification ID

Trees (05C05) Infinite graphs (05C63)

Cites Work

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

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)