Clean H-free classes from finite families
Question: finite families yielding clean H-free classes · arXiv:2212.02737
Status solved high confidence
The literal question is answered by the published array criterion: the H-free class is clean exactly when H-free n-arrays exist for only finitely many n.
Cited literature (1)
-
proof Induced subgraphs and tree decompositions XIII. Basic obstructions in H-free graphs for finite H (2024)
The literal question is answered by the published array criterion: the H-free class is clean exactly when H-free n-arrays exist for only finitely many n.
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 is not a direct finite structural classification of the forbidden family, and no new proof of the deep array theorem is given here.
Context
After proving Theorem 1.5 — which characterizes all single graphs $H$ for which the class $\mathcal{F}_H$ of $H$-free graphs is clean (precisely the subdivided star forests) — the authors pose the next natural step. They observe that any finite set $\mathcal{H}$ containing a subdivided star forest yields a clean class, but note that the converse fails (e.g., $\mathcal{H}=\{H, K_3\}$ for the unique double star on six vertices is also clean). A full description is deferred to a companion paper [6] by four of the five authors.
Notes. Posed as a natural next step in running prose (no labelled theorem environment). The companion paper [6] is announced to resolve it; PDF source is truncated after Section 2, so later sections may contain additional items not captured here.
Source paper
Induced subgraphs and tree-decompositions VII. Basic obstructions in $H$-free graphs
Tara Abrishami, Bogdan Alecu, Maria Chudnovsky, Sepehr Hajebi, Sophie Spirkl · 2023-11-07
https://arxiv.org/abs/2212.02737
PDF source