Loading problem…
Status
On this page
Status
Topics
Problem 58
If is a graph which contains odd cycles of different lengths then , with equality if and only if contains .
Source: erdosproblems.com/58
- Graph theory
- Chromatic number
- Cycles
Status
Solved, ProvedAn accepted solution exists. The statement is true.
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.