ε-restricted union cover for H-free graphs

Union cover variant (open problem) · arXiv:2105.07370

arXiv Informal medium confidence— first stated 2022-08-03

Authors: Maria Chudnovsky, Alex Scott, Paul Seymour, Sophie Spirkl

Status open high confidence

The conjecture asks whether for every graph $H$ and $\varepsilon > 0$, every $H$-free graph's vertex set can be covered (not necessarily partitioned) by a bounded number of $\varepsilon$-restricted subsets. The source paper (published in J. Combin. Theory Ser. B 163, 2023) explicitly identifies this as an open problem intermediate between their Theorem 1.3 and main Theorem 1.4, noting it does not obviously imply the stronger partition result. No follow-up paper resolving this conjecture was found in searches of the indexed literature through May 2026.

Reviewer notes. No follow-up found. The paper appeared on arXiv in May 2021 and was published in J. Combin. Theory Ser. B 163:256–271 (2023). The conjecture is explicitly labelled open in the source paper, sitting between Theorem 1.3 (partition into weakly ε-restricted sets) and Theorem 1.4 (partition into ε-restricted sets); the authors remark it does not seem easy and does not obviously imply 1.4. Sophie Spirkl's arXiv listing shows no subsequent paper on this topic; Semantic Scholar citation data was inconclusive.

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

Informal. For every graph $H$, and all $\varepsilon > 0$, there is an integer $N$ such that for every $H$-free graph $G$, $V(G)$ is the union of at most $N$ $\varepsilon$-restricted subsets (not necessarily pairwise disjoint).

Context

The authors note this as a statement midway between Theorem 1.3 (partition into weakly $\varepsilon$-restricted sets) and their main Theorem 1.4 (partition into $\varepsilon$-restricted sets). They remark that 'this variation does not seem to be easy, although it does not imply 1.4 as far as we know.'

Notes. Stated as a passing remark without a labelled environment; the authors signal it is open and non-trivial but do not explicitly phrase it as a conjecture or question.

Source paper

Strengthening Rodl's theorem
Maria Chudnovsky, Alex Scott, Paul Seymour, Sophie Spirkl · 2022-08-03
https://arxiv.org/abs/2105.07370 PDF source