Ubiquity in graphs III: Ubiquity of locally finite graphs with extensive tree-decompositions
Ubiquity in graphs III: Ubiquity of locally finite graphs with extensive tree-decompositions
复制标题
图 III 中的普遍性：具有广泛的树分解的局部有限图的普遍性
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Maximilian Teegen
中科院分区：
文献类型：
--
作者：
N. Bowler;C. Elbracht;Joshua Erde;J. P. Gollin;K. Heuer;Max Pitz;Maximilian Teegen
如果每个包含任意多个不相交 G 小数的图 Γ 自动包含无限多个不相交 G 小数，则称图 G 是普遍存在的。 Andreae 著名的普遍存在猜想认为，每个局部有限图都是普遍存在的。在本文中，我们证明了允许某种类型的树分解（我们称之为扩展树分解）的局部有限图是普遍存在的。特别是，这包括有限树宽度的所有局部有限图，以及具有有限多端的所有局部有限图，所有这些都具有有限度。每个局部有限图是否都允许广泛的树分解仍然是一个悬而未决的问题。
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 treedecomposition, 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.