Product structure open problem for sublinear separators

Open Problem 6 · arXiv:2208.10074

arXiv Problem low 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. [Statement not available: only the theorem-environment label was provided in the input, not the body text of the environment.]

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.

Notes. Exact statement text was not included in the provided input; only the environment label '[open] Open Problem 6' appeared in the theorem-environment list. Confidence is low because the statement could not be verified.

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