Product structure of graph classes with strongly sublinear separators

MaRDI QIDQ6408433zbMATH OpenFDO

Authors Zdeněk Dvořák, David R. Wood

Publication date 22 August 2022

Abstract: 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 $mathcalG$ admits $O(n^{1-epsilon})$ separators, then for any fixed $deltain(0,epsilon)$ every $n$-vertex graph in $mathcalG$ 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(loglogn)$. We prove a product strengthening of the result of Dvov{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.

This page was built for publication: Product structure of graph classes with strongly sublinear separators

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6408433)