首页 | 本学科首页   官方微博 | 高级检索  
     


Vertex-disjoint rainbow triangles in edge-colored graphs
Abstract:Let G be an edge-colored graph of order n. The minimum color degree of G, denoted by δc(G), is the largest integer k such that for every vertex v, there are at least k distinct colors on edges incident to v. We say that an edge-colored graph is rainbow if all its edges have different colors. In this paper, we consider vertex-disjoint rainbow triangles in edge-colored graphs. Li (2013) showed that if δc(G)(n+1)2, then G contains a rainbow triangle and the lower bound is tight. Motivated by this result, we prove that if n20 and δc(G)(n+2)2, then G contains two vertex-disjoint rainbow triangles. In particular, we conjecture that if δc(G)(n+k)2, then G contains k vertex-disjoint rainbow triangles. For any integer k2, we show that if n16k12 and δc(G)n2+k1, then G contains k vertex-disjoint rainbow triangles. Moreover, we provide sufficient conditions for the existence of k edge-disjoint rainbow triangles.
Keywords:Edge-colored graph  Rainbow triangles  Color degree
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号