On Odd Rainbow Cycles in Edge-Colored Graphs

Abstract

Let $G=(V,E)$ be an $n$-vertex edge-colored graph. In 2013, H. Li proved that if every vertex $v\in V$ is incident to at least $(n+1)/2$ distinctly colored edges, then $G$ admits a rainbow triangle. We prove that the same hypothesis ensures a rainbow $\ell$-cycle $C_{\ell }$ whenever $n\ge 432\ell$. This result is sharp for all odd integers $\ell \ge 3$, and extends earlier work of the authors for when $\ell$ is even.

10 pages