2020/12/24 by Nathan Bowler, Bowler, Nathan, Christian Elbracht +11
Computer Science · Mathematics · #05C63 #05C83 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2012.13070
openalex publication_date 2020/12/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A graph G is said to be ubiquitous, if every graph Γ that contains arbitrarily many disjoint G-minors automatically contains infinitely many disjoint G-minors. The well-known Ubiquity conjecture of Andreae says that every locally finite graph is ubiquitous. In this paper we show that locally finite graphs admitting a certain type of tree-decomposition, which we call an extensive tree-decomposition, are ubiquitous. In particular this includes all locally finite graphs of finite tree-width, and also all locally finite graphs with finitely many ends, all of which have finite degree. It remains an open question whether every locally finite graph admits an extensive tree-decomposition.