Polynomial expansion and sublinear separators

Abstract

Let $\mathcal{C}$ be a class of graphs that is closed under taking subgraphs. We prove that if for some fixed $0<\delta \le 1$, every $n$-vertex graph of $\mathcal{C}$ has a balanced separator of order $O(n^{1-\delta })$, 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((k\text{ polylog }k{)}^{1/\delta })$. This confirms a conjecture of Dvořák and Norin.

6 pages, no figure

Cited by in corpus (3)

• Notes on Graph Product Structure Theory
• Improved bounds for weak coloring numbers
• Universality in minor-closed graph classes