It is easy to see that every $q$-edge-colouring of the complete graph on $2^q+1$ vertices must contain a monochromatic odd cycle. A natural question raised by Erd\H{ o}s and Graham in $1973$ asks for the smallest $L(q)$ such that every $q$-edge-colouring of $K_{ 2^q+1}$ must contain a monochromatic odd cycle of length at most $L(q)$. In here, we show that $L(q)=O\left(\frac{ 2^q}{ q^{ 1-o(1)}}\right)$ giving the first non-trivial upper bound on $L(q)$.
Categories: math.CO