高维球交图的强次线性分隔器及有界渐近维数
Strongly sublinear separators and bounded asymptotic dimension for sphere intersection graphs
摘要 Abstract
本文研究了$d\geq 2$时$\mathbb{R}^d$中的球交图类$\mathcal{C}^d$。我们证明,对于每个整数$t$,在$\mathcal{C}^d$中排除$K_{t,t}$为子图的所有图类具有强次线性分隔器。此外,我们还证明$\mathcal{C}^d$的渐近维数至多为$2d+2$。
In this paper, we consider the class $\mathcal{C}^d$ of sphere intersection graphs in $\mathbb{R}^d$ for $d \geq 2$. We show that for each integer $t$, the class of all graphs in $\mathcal{C}^d$ that exclude $K_{t,t}$ as a subgraph has strongly sublinear separators. We also prove that $\mathcal{C}^d$ has asymptotic dimension at most $2d+2$.