Consecutive holes in bounded clique number graphs

Informal Conjecture (generalization of 1.3 to bounded clique number) · arXiv:1509.06563

arXiv Informal medium confidence— first stated 2018-02-12

Status open high confidence

The conjecture — that for all ν > 0 and k ≥ 3 there exists n such that every graph with no k-clique and chromatic number ≥ n contains ν consecutive hole lengths — remains open. The source paper (arXiv:1509.06563) proves the triangle-free case (k=3) but explicitly states no progress on the general bounded-clique-number extension. A wide web search found no subsequent paper resolving or substantially advancing the full conjecture; related progress (e.g. arXiv:1701.07217 on long odd holes in Kk-free graphs) concerns different hole properties and does not settle consecutive lengths for general k.

Reviewer notes. No follow-up resolving the bounded-clique-number generalization was found in the indexed literature. The sole internal reference (arXiv:2306.02364) is about tournament structure and is unrelated to this conjecture. The conjecture is from 2018 and remains open with high confidence.

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

Informal. The corresponding result to 1.3 is true for graphs with bounded clique number rather than just triangle-free graphs: for all integers $\nu > 0$ and $k \geq 3$ there exists $n$ such that if $G$ has no clique of cardinality $k$ and has chromatic number at least $n$, then for some $t$, $G$ has a hole of length $t+i$ for $1 \leq i \leq \nu$.

Context

Immediately after the statement of the main result (1.3), which establishes $\nu$ consecutive hole lengths for triangle-free graphs, the authors conjecture the same conclusion holds under the weaker assumption that $G$ has bounded clique number. They note they have made no progress in proving this.

Notes. PDF source — exact statement inferred from prose; the phrase 'the corresponding result' refers to Theorem 1.3 in context

Source paper

Induced subgraphs of graphs with large chromatic number. IV. Consecutive holes
Alex Scott, Paul Seymour · 2018-02-12
https://arxiv.org/abs/1509.06563 PDF source