Rainbow triangles in edge-colored complete graphs

arXiv2012.01716MaRDI QIDQ6355201FDOQ6355201

Authors: Xiaozheng Chen, Xueliang Li 

Publication date: 3 December 2020

Abstract: Let $G$ be a graph of order $n$ with an edge-coloring $c$, and let $delt{a}^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 $delt{a}^c(G)geqfracn+12$, then every vertex of $G$ is contained in a rainbow triangle. In this paper, we show that if $delt{a}^c(G)geqfracn+k2$, 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 $delt{a}^c(G)geqfracn+12$, then $G$ contains a rainbow triangle. We show that if $G$ is complete and $delt{a}^c(G)geqfracn2$, then $G$ contains a rainbow triangle and the bound is sharp. Hu et al. showed that for an edge-colored graph $G$ of order $ngeq20$, if $delt{a}^c(G)geqfracn+22$, then $G$ contains two vertex-disjoint rainbow triangles. We show that if $G$ is complete with order $ngeq8$ and $delt{a}^c(G)geqfracn+12$, then $G$ contains two vertex-disjoint rainbow triangles. Moreover, we improve the result of Hu et al. from $ngeq20$ to $ngeq7$, the best possible.

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38)

This page was built for publication: Rainbow triangles in edge-colored complete graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6355201)