Product structure open problem for sublinear separators

Open Problem 6 · arXiv:2208.10074

arXiv Problem high confidence— first stated 2023-09-27

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

Status partial medium confidence

Open Problem 6 asks whether for any hereditary graph class \mathcal{G} with \operatorname{sep}(\mathcal{G}) \in O(n^{1-\varepsilon}), there exists a constant c = c(\mathcal{G}) such that every n-vertex graph G \in \mathcal{G} is contained in H \boxtimes K_m where \operatorname{tw}(H) \leq c and m \in O(n^{1-\varepsilon}). The source paper itself already confirms the answer affirmatively for graphs excluding a fixed minor (Theorem 7, citing Distel et al. 2022). The 2024 paper by Liu, Norin, and Wood (arXiv:2410.20333) further extends this to graphs excluding a fixed odd minor. The general hereditary case with strongly sublinear separators remains open.

Cited literature (1)

partial Product Structure and Tree-Decompositions (2024)

Chun-Hung Liu, Sergey Norin, David R. Wood · arXiv preprint · arXiv:2410.20333

Proves that graphs excluding a fixed odd minor are contained in the strong product of two graphs each with bounded treewidth, extending partial progress on Open Problem 6 to odd-minor-free hereditary classes (which have strongly sublinear separators).

Reviewer notes. Open Problem 6 is already partially resolved within the source paper itself for excluded-minor classes (Theorem 7). Post-publication, arXiv:2410.20333 adds partial progress for odd-minor-free classes. No paper was found resolving the general hereditary case. Confidence is medium rather than high because the problem is ~3 years old and there may be further progress not surfaced by these searches.

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

Problem. For any hereditary graph class $\mathcal{G}$ with separation-number $\operatorname{sep}(\mathcal{G})\in O(n^{1-\epsilon})$, does there exist a constant $c=c(\mathcal{G})$ such that every $n$-vertex graph $G\in\mathcal{G}$ is contained in $H\boxtimes K_m$, where $\operatorname{tw}(H)\leqslant c$ and $m\in O(n^{1-\epsilon})$.

Context

Open Problem 6 is the only explicitly labeled open-problem environment in the paper (LaTeX environment type [open]). It appears between Theorem 5 and Theorem 7, in the context of product structure theory for graph classes with strongly sublinear separators.

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