
























Let $\mathcal{C}$ be a class of graphs that is closed under taking subgraphs. We prove that if for some fixed $0<δ\le 1$, every $n$-vertex graph of $\mathcal{C}$ has a balanced separator of order $O(n^{1-δ})$, then any depth-$k$ minor (i.e. minor obtained by contracting disjoint subgraphs of radius at most $k$) of a graph in $\mathcal{C}$ has average degree $O\big((k \text{ polylog }k)^{1/δ}\big)$. This confirms a conjecture of Dvořák and Norin.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。