Product structure with bounded tree-depth separators

Conjecture (product structure with bounded tree-depth and tight clique size) · arXiv:2208.10074

arXiv Conjecture low confidence— first stated 2023-09-27

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

Status open high confidence

The conjecture in its strongest form — that every n-vertex graph in a hereditary class with O(n^{1-\epsilon}) separators is a subgraph of the strong product of a graph H with bounded (constant) tree-depth and a complete graph of size O(n^{1-\epsilon}) — remains open. The source paper itself proves two approximations: constant tree-depth with clique size O(n^{1-\epsilon+\delta}) for any \delta > 0, and exact clique size O(n^{1-\epsilon}) with tree-depth O(\log\log n); both gaps are shown to be inherent via isoperimetric inequalities on grid graphs. No subsequent paper resolving the full conjecture was found in a search covering arXiv through 2026.

Reviewer notes. Search found two potentially related post-2023 arXiv papers: 2410.20333 (Liu, Norin, Wood, 'Product Structure and Tree-Decompositions', Oct 2024) addresses minor-excluded graphs via strong products of bounded-treewidth digraphs, and 2502.20182 (Abrishami et al., 'On coarse tree decompositions and coarse balanced separators', Feb 2025) studies coarse balanced separators — neither was verified to address the specific conjecture about constant tree-depth with tight clique size O(n^{1-\epsilon}).

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Conjecture. For any hereditary graph class $\mathcal{G}$ that admits $O(n^{1-\epsilon})$ separators, 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})$.

Context

The abstract states that the paper investigates this conjecture. The proven results in the paper achieve the conclusion either with an extra $n^{\delta}$ factor in the clique size (for $H$ with constant tree-depth, any fixed $\delta\in(0,\epsilon)$) or with tree-depth $O(\log\log n)$ for $H$ when $\delta=0$; moreover, both limitations are shown to be best possible via isoperimetric inequalities for grid graphs. The conjecture in its strongest form — constant tree-depth of $H$ with clique size exactly $O(n^{1-\epsilon})$ — is investigated but not fully resolved.

Notes. The abstract is cut off mid-sentence before the conjecture is completed ('every $n$...'). The statement above is partially reconstructed from the surrounding context in the abstract. It may not match the exact wording in the body of the paper.

Source paper

Product structure of graph classes with strongly sublinear separators
Zdeněk Dvořák, David R. Wood · 2023-09-27
https://arxiv.org/abs/2208.10074