Consecutive hole lengths for bounded clique number

Conjecture 1.8 · arXiv:1705.04609

arXiv Conjecture high confidence— first stated 2018-12-04

Status open high confidence

Conjecture 1.8 from arXiv:1705.04609 — that every graph with bounded clique number and sufficiently large chromatic number contains holes of ℓ consecutive lengths — remains open as of May 2026. The source paper itself provides Theorem 1.9 as the best known partial result, guaranteeing two holes of consecutive lengths both greater than ℓ. A web search capped at 5 calls returned no subsequent paper verifiably resolving the full conjecture; the related Gyárfás conjecture on long odd holes was resolved by arXiv:1701.07217 but addresses a distinct statement.

Reviewer notes. Web search explicitly returned the assessment that this conjecture remains open, with the only partial result being Theorem 1.9 of the source paper (two holes of consecutive lengths both greater than ℓ). arXiv:2303.11231 (published in Advances in Combinatorics 2025:2) appeared in a relevant search but could not be verified with a WebFetch call within the 5-call cap and so is not cited. All five internal references appear to be mismatched to other conjectures (Hadwiger, Albertson, Erdős–Pósa property, tournament structure); only arXiv:1701.07217 belongs to the same research line but resolves Gyárfás's conjecture on long odd holes rather than Conjecture 1.8.

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

Conjecture. For all integers $\kappa, \ell \geq 0$, there exists $c \geq 0$ such that every graph with chromatic number greater than $c$ contains either a complete subgraph on $\kappa$ vertices or holes of $\ell$ consecutive lengths.

Context

The authors proved in [14] (a prior paper in this series) that every triangle-free graph with sufficiently large chromatic number contains holes of $\ell$ consecutive lengths (result 1.7 of the present paper). Conjecture 1.8 extends this to graphs with clique number bounded by any $\kappa$. The conjecture remains open; this paper makes a partial step by proving 1.9, which guarantees holes of two consecutive lengths both greater than $\ell$.

Notes. Explicitly labelled 'Conjecture' in the paper. The authors state it was conjectured in their earlier paper [14]; the theorem header carries no parenthetical attribution, so classified as 'states' per schema rules. Theorem 1.9 of this paper (holes of two consecutive long lengths) is proved as a step towards this conjecture.

Source paper

Induced subgraphs of graphs with large chromatic number. X. Holes of specific residue
Alex Scott, Paul Seymour · 2018-12-04
https://arxiv.org/abs/1705.04609 PDF source