On sufficient conditions for rainbow cycles in edge-colored graphs

Abstract

Let $G$ be an edge-colored graph. We use $e(G)$ and $c(G)$ to denote the number of edges of $G$ and the number of colors appearing on $E(G)$, respectively. For a vertex $v\in V(G)$, the \emph{color neighborhood} of $v$ is defined as the set of colors assigned to the edges incident to $v$. A subgraph of $G$ is \emph{rainbow} if all of its edges are assigned with distinct colors. The well-known Mantel's theorem states that a graph $G$ on $n$ vertices contains a triangle if $e(G)\ge \lfloor \frac{n^2}{4}\rfloor +1$. Rademacher (1941) showed that $G$ contains at least $\lfloor \frac{n}{2}\rfloor$ triangles under the same condition. Li, Ning, Xu and Zhang (2014) proved a rainbow version of Mantel's theorem: An edge-colored graph $G$ has a rainbow triangle if $e(G)+c(G)\ge n(n+1)/2$. In this paper, we first characterize all graphs $G$ satisfying $e(G)+c(G)\ge n(n+1)/2-1$ but containing no rainbow triangles. Motivated by Rademacher's theorem, we then characterize all graphs $G$ which satisfy $e(G)+c(G)\ge n(n+1)/2$ but contain only one rainbow triangle. We further obtain two results on color neighborhood conditions for the existence of rainbow short cycles. Our results improve a previous theorem due to Broersma, Li, Woeginger, and Zhang (2005). Moreover, we provide a sufficient condition in terms of color neighborhood for the existence of a specified number of vertex-disjoint rainbow cycles.

19 pages, 2 figures, to appear in Discrete Mathematics