On sufficient conditions for rainbow cycles in edge-colored graphs

摘要

Let $G$ be an edge-colored graph. For a vertex $vin V(G)$, the emph{colordegree} of $v$ is defined as the number of different colors assigned to theedges incident to $v$. The emph{color neighborhood} of $v$ is defined as theset of colors assigned to edges incident to $v$. We also denote by $c(G)$ thenumber of different colors appearing on $E(G)$. A subgraph of $G$ isemph{rainbow} if all the edges in it are assigned different colors. In this paper, we consider rainbow versions of some classical results on theexistence of cycles. To obtain a rainbow version of Mantel's theorem, Li, Ning,Xu and Zhang (2014) proved that $G$ has a rainbow triangle if $e(G)+c(G)geqn(n+1)/2$. In this paper, we first characterize all graphs $G$ with no rainbowtriangles such that $e(G)+c(G)geq n(n+1)/2-1$. Motivated by the relationshipbetween Mantel's theorem and Rademacher's theorem, we then show that $G$contains at least two rainbow triangles if $e(G)+c(G)geq n(n+1)/2$ unless $G$belongs to a well characterized class of edge-colored graphs. We also discusscolor neighborhood conditions for the existence of rainbow short cycles. Ourresults improve a previous theorem by Broersma et al. Moreover, we give asufficient condition for the existence of specified number of vertex-disjointrainbow cycles in terms of color neighborhood conditions.