Erdős Problem #921

Let \(k\geq 4\) and let \(f_k(n)\) be the largest \(m\) such that there is a graph on \(n\) vertices with chromatic number \(k\) in which every odd cycle has length \(> m\). Then \[f_k(n) \asymp n^{\frac{1}{k-2}}.\] A question of Erdős and Gallai. Proved for all \(k\geq 4\) by Kierstead, Szemerédi, and Trotter [KST84]. The linked formal proof (Codex and GPT-5.6 Sol) states this as `f k n = Θ(n ^ (1 / (k - 2)))`, where `f k n` is the largest `m` such that some graph on `n` vertices with chromatic number `k` has no odd cycle of length at most `m`; the two eventual statements below are the two halves of this estimate.