Product structure of graph classes with strongly sublinear separators

We investigate the product structure of hereditary graph classes admitting strongly sublinear separators. We characterise such classes as subgraphs of the strong product of a star and a complete graph of strongly sublinear size. In a more precise result, we show that if any hereditary graph class $\mathcal{G}$ admits $O(n^{1-\epsilon})$ separators, then for any fixed $\delta\in(0,\epsilon)$ every $n$-vertex graph in $\mathcal{G}$ is a subgraph of the strong product of a graph $H$ with bounded tree-depth and a complete graph of size $O(n^{1-\epsilon+\delta})$. This result holds with $\delta=0$ if we allow $H$ to have tree-depth $O(\log\log n)$. We prove a product strengthening of the result of Dvo\v{r}\'ak and Norin [SIAM J. Discrete Math., 2016] for graphs of polynomial expansion. Finally, we prove that $n$-vertex graphs of bounded treewidth are subgraphs of the product of a graph with tree-depth $d$ and a complete graph of size $O(n^{1/d})$, which is best possible.