Problem 921

../

claims/: The 1 claim page of Problem 921, one per claimant's result; the problem's standing derives from them.

---

Statement. 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}}?$$

Status. Proved. The site credits Kierstead, Szemerédi and Trotter [KST84] with the proof for every $k\ge4$ (claim page): 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.

Source. erdosproblems.com/921, accessed 2026-09-04. Cite as: T. F. Bloom, Erdős Problem #921, https://www.erdosproblems.com/921.

References.

• [Ga63] Gallai, T., [[../library/graph_coloring/gallai_1963_kritische_graphen_i/_index|Kritische Graphen. I]]. Magyar Tud. Akad. Mat. Kutató Int. Közl. 8 (1963), 165-192.
• [KST84] Kierstead, H. A. and Szemerédi, E. and Trotter, Jr., W. T., On coloring graphs with locally small chromatic number. Combinatorica 4 (1984), no. 2-3, 183-185.

Formalization. Statement in formal-conjectures; solution in Erdos921.lean in Boris Alexeev's lean-proofs repository.

Progress

Not yet compiled.

Known Results

Not yet compiled.

Linked library material

These entries are derived from explicit links on library pages. They are navigation only and do not by themselves record mathematical progress.

• erdos_1979_problems_results_graph_theory_combinatorial_analysis
• erdos_1979_problems_results_graph_theory_combinatorial_analysis / conjecture_p154
• gallai_1963_kritische_graphen_i
• gallai_1963_kritische_graphen_i / item_2_4