Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated Oct 8

Problem 58

claims/: The 2 claim pages of Problem 58, one per claimant's result; the problem's standing derives from them.

Statement. If $G$ is a graph which contains odd cycles of $\leq k$ different lengths then $\chi(G)\leq 2k+2$ , with equality if and only if $G$ contains $K_{2k+2}$ .

Status. The site labels the problem proved, crediting Gyárfás [Gy92]. The accepted claim is Gyárfás's bound with its equality case; the strengthening by Gao, Huo and Ma [GaHuMa21] is an accepted partial claim, consecutive odd cycle lengths, covering the inequality but not the equality case.

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

References.

[GaHuMa21] Gao, Jun and Huo, Qingyi and Ma, Jie, A strengthening on odd cycles in graphs of given chromatic number. SIAM J. Discrete Math. 35 (2021), no. 4, 2317-2327, DOI 10.1137/20M1387882.
[Gy92] Gyárfás, A., [[../library/graph_coloring/gyarfas_1992_graphs_k_odd_cycle_lengths/_index|Graphs with k odd cycle lengths]]. Discrete Math. (1992), 41-48.

Formalization. Statement in formal-conjectures, added on 2026-09-09, after the site access. The Lean development that declares itself a formalization of Gyárfás's solution is linked from his claim page.

Current assessment

The question, in the site's formulation accessed, asks whether a graph whose odd cycles have at most $k$ distinct lengths has chromatic number at most $2k+2$ , with equality exactly when it contains $K_{2k+2}$ . The answer is yes: the accepted claim is Gyárfás's bound with its equality case, refereed in Discrete Math. 103 (1992) and credited by the site's curator, and the standing is solved with claim proved. Gao, Huo and Ma's consecutive odd lengths (claim page) are an accepted partial claim on the inequality alone. The site's remark that Bollobás and Shelah confirmed the case $k=1$ has no claim page: the check is reported by Gyárfás and by the site, has no publication of its own, and Gyárfás's theorem covers $k=1$ .

Search scope: the site's problem page and its commentary, the community database (which lists the problem as proved and its statement as formalized as of its last update), the formal-conjectures statement file (added 2026-09-09, proof left as sorry, no formal proof named) and the Lean development in Boris Alexeev's lean-proofs collection linked from Gyárfás's claim page.

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.

Linked from (10)

Chromatic number at most 2k+2 from k odd cycle lengths Consecutive odd cycle lengths from chromatic number problems/graph_coloring/E0058/claims Graph Coloring graph_coloring/gao_2021_strengthening_odd_cycles_graphs_given_chromatic Theorem 1.2 (p. 1): for k >= 6, chromatic number k+1 forces k cycles of consecutive lengths unless some block is K_{k+1}Theorem 1.3 (p. 2): chromatic number k+1 >= 3 forces cycles of lengths 2m+1, ..., 2m+k-1 for some m graph_coloring/gyarfas_1992_graphs_k_odd_cycle_lengths Corollary: k odd cycle lengths give chromatic number at most 2k+2 Theorem 1: a 2-connected graph with k odd cycle lengths and minimum degree at least 2k+1 is K_{2k+2}

Graph