A problem of Erdős and Graham. The edges of $K_{2^n}$ can be $n$-coloured to avoid odd cycles of any length. It can be shown that $C_5$ and $C_7$ can be avoided for large $n$.

Chung [Ch97] asked whether $f(n)\to \infty$ as $n\to \infty$. Day and Johnson [DaJo17] proved this is true, and that\[f(n)\geq 2^{c\sqrt{\log n}}\]for some constant $c>0$. The trivial upper bound is $2^n$.

Girão and Hunter [GiHu24] have proved that\[f(n) \ll \frac{2^n}{n^{1-o(1)}}.\]Janzer and Yip [JaYi25] have improved this to\[f(n) \ll n^{3/2}2^{n/2}.\]See also the entry in the graphs problem collection.

View the LaTeX source