Rainbow cycles in triangle-free graphs

Abstract

Let $G=(V,E)$ be an edge-colored graph, and let $\hat{I}{´}^c(G)={\min }_{v\in V}\{d^c(v)\}$ where $d^c(v)$ is the number of colors on edges incident to a vertex $v$. We show that for a sufficiently large $n$ if $G$ is an edge-colored triangle-free graph of order $n$ that satisfies $\hat{I}{´}^c(G)\ge (n+7)/5$, then $G$ contains a rainbow cycle of length four, which improves a bound of Ding et al. and is best possible. In addition, we show that given $k$, there is $n_0$ such that for $n\ge n_0$, if $G$ is an edge-colored triangle-free graph with $\hat{I}{´}^c(G)>n/5+3$, then $G$ contains a rainbow cycle of length $4k$.

20 pages, 4 figures