If a graph G contains odd cycles of at most k different lengths, must chi(G)≤2k+2, with equality only when G contains K_2k+2?

Erdős Problem #58 — Chromatic number from the number of odd cycle lengths

If a graph $G$ contains odd cycles of at most $k$ different lengths, must $\chi(G)\leq2k+2$ , with equality only when $G$ contains $K_{2k+2}$ ?

References

A. Gyárfás, Graphs with k odd cycle lengths, Discrete Mathematics 103 (1992), 41–48.

Posted 1 month ago

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

No solutions have been posted yet.