χ-boundedness via odd cycle exclusion

Question 1.1 · arXiv:2503.20045

arXiv Question high confidence— first stated 2025-03-25

Authors: Hidde Koerts, Benjamin Moore, Sophie Spirkl

Status solved high confidence

Question 1.1 is the chromatic-threshold problem for odd cycles: for which ε>0 and k>0 does every graph with minimum degree at least ε|V(G)| that contains no C_{2k+1} have bounded chromatic number? This is fully resolved by pre-existing literature cited in the source paper itself. Thomassen proved the answer affirmative for k≥2 at all ε>0 and for k=1 at all ε>1/3; Erdős–Simonovits–Hajnal showed no such bound exists for k=1 when ε<1/3; and Allen, Böttcher, Griffiths, Kohayakawa, and Morris completely resolved the chromatic-threshold problem for all fixed graphs. The question is presented as known background motivation for the paper's novel digraph generalization.

Reviewer notes. Question 1.1 is resolved entirely by literature predating the source paper; no post-2025 follow-up is needed or found. The complete resolution comes from Thomassen (affirmative cases) and Allen–Böttcher–Griffiths–Kohayakawa–Morris (full chromatic threshold characterisation for all graphs). The source paper's contribution is the digraph analogue of this result, published in Combinatorica (March 2026). arXiv:2511.18961 (Wang, 2025) addresses related cycle-length and minimum-degree questions but does not reference 2503.20045 or this specific question.

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

Question. For which $\varepsilon>0$ and $k>0$ does there exist a bound $c$ such that each simple graph $G$ either contains $C_{2k+1}$ as a subgraph or $\chi(G)\leq c$ (or both)?

Context

Erdős and Simonovits (1972) asked whether every graph with no fixed odd cycle and large minimum degree has bounded chromatic number, specifically for triangles and $C_5$. The paper authors present Question 1.1 as a generalization of those questions. Thomassen subsequently answered it affirmatively for $C_3$ at $\varepsilon>1/3$ and for all longer odd cycles at all $\varepsilon>0$.

Notes. Presented as background context; the specific cases addressed by Thomassen [11,12] are resolved, but the fully general formulation is posed by the paper authors as a unifying question.

Source paper

Orientations of cycles in digraphs of high chromatic number and high minimum out-degree
Hidde Koerts, Benjamin Moore, Sophie Spirkl · 2025-03-25
https://arxiv.org/abs/2503.20045