Abstract
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.
Original language | English |
---|---|
Article number | 3 |
Journal | Combinatorial Theory |
Volume | 4 |
Issue number | 2 |
Number of pages | 52 |
ISSN | 2766-1334 |
DOIs | |
Publication status | Published - 2024 |
Keywords
- Graph minors
- Infinite graphs
- Ubiquity