ε-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 solved high confidence

The partition theorem stated in the source paper immediately gives the requested union cover, because every partition is a cover.

Cited literature (1)

proof Strengthening Rödl's theorem (2021)

See linked article · Existing literature or final source version

The partition theorem stated in the source paper immediately gives the requested union cover, because every partition is a cover.

Read the literature-status audit

Reviewer notes. These status corrections report results attributed to existing papers or to the final source version. Graph-Theory-LLM-Proofs located and checked the implication; it is not credited as the author of the result. Audit caveat: This assumes the catalog uses the same induced-H-free and ε-restricted definitions and the same dependence N=N(H,ε) as the quoted source.

Auto-reviewed 2026-08-31 with gpt-5.6-sol.

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