2020/12/03 by Xiaozheng Chen, Xueliang Li, Chen, Xiaozheng +1
Computer Science · Mathematics · #05C15 #05C38 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2012.01716
openalex publication_date 2020/12/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G be a graph of order n with an edge-coloring c, and let δ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 δc(G)≥ (n+1)/(2), then every vertex of G is contained in a rainbow triangle. In this paper, we show that if δc(G)≥ (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 δc(G)≥ (n+1)/(2), then G contains a rainbow triangle. We show that if G is complete and δc(G)≥ (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≥ 20, if δc(G)≥ (n+2)/(2), then G contains two vertex-disjoint rainbow triangles. We show that if G is complete with order n≥ 8 and δc(G)≥ (n+1)/(2), then G contains two vertex-disjoint rainbow triangles. Moreover, we improve the result of Hu et al. from n≥ 20 to n≥ 7, the best possible.