Product structure of graph classes with strongly sublinear separators

08/22/2022

∙

by   David R. Wood, et al.

∙

0

∙

share

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 𝒢 admits O(n^1-ϵ) separators, then for any fixed δ∈(0,ϵ) every n-vertex graph in 𝒢 is a subgraph of the strong product of a graph H with bounded tree-depth and a complete graph of size O(n^1-ϵ+δ). This result holds with δ=0 if we allow H to have tree-depth O(loglog n). We prove a product strengthening of the result of Dvořák 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.