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 𝒢 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(loglogn). Moreover, using extensions of classical isoperimetric inequalties for grids graphs, we show the dependence on δ in our results and the above td(H)∈O(loglogn) bound are both best possible. We prove that n-vertex graphs of bounded treewidth are subgraphs of the product of a graph with tree-depth t and a complete graph of size O(n 1/t ), which is best possible. Finally, we investigate the conjecture that for any hereditary graph class 𝒢 that admits O(n 1-ϵ ) separators, every n-vertex graph in 𝒢 is a subgraph of the strong product of a graph H with bounded tree-width and a complete graph of size O(n 1-ϵ ). We prove this for various classes 𝒢 of interest.