Rainbow triangles in edge-colored complete graphs

Abstract

Let $G$ be a graph of order $n$ with an edge-coloring $c$, and let ${\delta }^c(G)$ denote the minimum color-degree of $G$. A subgraph $F$ of $G$ is called rainbow if any two edges of $F$ have distinct colors. There have been a lot results in the existing literature on rainbow triangles in edge-colored complete graphs. Fujita and Magnant showed that for an edge-colored complete graph $G$ of order $n$, if ${\delta }^c(G)\ge \frac{n+1}{2}$, then every vertex of $G$ is contained in a rainbow triangle. In this paper, we show that if ${\delta }^c(G)\ge \frac{n+k}{2}$, then every vertex of $G$ is contained in at least $k$ rainbow triangles, which can be seen as a generalization of their result. Li showed that for an edge-colored graph $G$ of order $n$, if ${\delta }^c(G)\ge \frac{n+1}{2}$, then $G$ contains a rainbow triangle. We show that if $G$ is complete and ${\delta }^c(G)\ge \frac{n}{2}$, then $G$ contains a rainbow triangle and the bound is sharp. Hu et al. showed that for an edge-colored graph $G$ of order $n\ge 20$, if ${\delta }^c(G)\ge \frac{n+2}{2}$, then $G$ contains two vertex-disjoint rainbow triangles. We show that if $G$ is complete with order $n\ge 8$ and ${\delta }^c(G)\ge \frac{n+1}{2}$, then $G$ contains two vertex-disjoint rainbow triangles. Moreover, we improve the result of Hu et al. from $n\ge 20$ to $n\ge 7$, the best possible.

10 pages, 4 figures

References in corpus (1)

• Vertex-disjoint properly edge-colored cycles in edge-colored complete graphs