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$ . Is it true that

f_k(n) \asymp n^{\frac{1}{k-2}}?

Source: erdosproblems.com/921

Graph theory
Chromatic number
Cycles

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

Proved. The site credits Kierstead, Szemerédi and Trotter [KST84] with the proof for every $k\ge4$ (claim page (Kierstead, Szemerédi and Trotter, 1984)): their local-coloring theorem gives $f_k(n)\ll_k n^{1/(k-2)}$ , and Schrijver's stable Kneser graphs give the matching lower bound. The question is Erdős and Gallai's; for $k=4$ , Gallai [Ga63] had the lower bound $f_4(n)\gg n^{1/2}$ for infinitely many $n$ , and the matching upper bound is an unpublished argument of Erdős.

Problem 921

Status

Proof claims

Discussion