Rainbow triangles in edge-colored complete graphs


Abstract in English

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)geq 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)geq 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)geq frac{n+1}{2}$, then $G$ contains a rainbow triangle. We show that if $G$ is complete and $delta^c(G)geq 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 $ngeq 20$, if $delta^c(G)geq frac{n+2}{2}$, then $G$ contains two vertex-disjoint rainbow triangles. We show that if $G$ is complete with order $ngeq 8$ and $delta^c(G)geq frac{n+1}{2}$, then $G$ contains two vertex-disjoint rainbow triangles. Moreover, we improve the result of Hu et al. from $ngeq 20$ to $ngeq 7$, the best possible.

Download