Counting rainbow triangles in edge-colored graphs

被引:0
作者
Li, Xueliang [1 ]
Ning, Bo [2 ]
Shi, Yongtang [1 ]
Zhang, Shenggui [3 ,4 ]
机构
[1] Nankai Univ, Ctr Combinator & LPMC, Tianjin, Peoples R China
[2] Nankai Univ, Coll Comp Sci, Tianjin 300350, Peoples R China
[3] Northwestern Polytech Univ, Sch Math & Stat, Xian, Shaanxi, Peoples R China
[4] Northwestern Polytech Univ, Xian Budapest Joint Res Ctr Combinator, Xian, Shaanxi, Peoples R China
基金
中国国家自然科学基金;
关键词
color degree; counting subgraphs; monochromatic degree; rainbow triangles; CYCLES; PATHS;
D O I
10.1002/jgt.23158
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Let G be an edge-colored graph on n vertices. The minimum color degree of G, denoted by dc (G), is defined as the minimum number of colors assigned to the edges incident to a vertex in G. In 2013, Li proved that an edge-colored graph G on n vertices contains a rainbow triangle if dc (G) = n + 1 2. In this paper, we obtain several estimates on the number of rainbow triangles through one given vertex in G. As a consequence, we prove counting results for rainbow triangles in edge-colored graphs. One main theorem states that the number of rainbow triangles in G is at least 1dc (G)(2dc (G) - n) n 6, which is best possible by considering the rainbow k-partite Turan graph, where its order is divisible by k. This means that there are O(n2) rainbow triangles in G if dc (G) = n + 1 2, and O(n3) rainbow triangles in G if =d G cn()c when c > 12. Both results are tight in the sense of the order of the magnitude. We also prove a counting version of a previous theorem on rainbow triangles under a color neighborhood union condition due to Broersma et al., and an asymptotically tight color degree condition forcing a colored friendship subgraph Fk (i.e., k rainbow triangles sharing a common vertex).
引用
收藏
页码:742 / 758
页数:17
相关论文
共 23 条
[1]  
ADA R, 2016, DISCRETE MATH, V339, P1387
[2]   Rainbow triangles and the Caccetta-Haggkvist conjecture [J].
Aharoni, Ron ;
DeVos, Matthew ;
Holzman, Ron .
JOURNAL OF GRAPH THEORY, 2019, 92 (04) :347-360
[3]  
Bondy J., 2008, GTM, V244, pxii+651, DOI DOI 10.1007/978-1-84628-970-5
[4]  
Broersma H, 2005, AUSTRALAS J COMB, V31, P299
[5]   Long rainbow paths and rainbow cycles in edge colored graphs - A survey [J].
Chen, He .
APPLIED MATHEMATICS AND COMPUTATION, 2018, 317 :187-192
[6]   On odd rainbow cycles in edge-colored graphs [J].
Czygrinow, Andrzej ;
Molla, Theodore ;
Nagle, Brendan ;
Oursler, Roy .
EUROPEAN JOURNAL OF COMBINATORICS, 2021, 94
[7]   Rainbow triangles and cliques in edge-colored graphs [J].
Ehard, Stefan ;
Mohr, Elena .
EUROPEAN JOURNAL OF COMBINATORICS, 2020, 84
[8]   EXTREMAL GRAPHS FOR INTERSECTING TRIANGLES [J].
ERDOS, P ;
FUREDI, Z ;
GOULD, RJ ;
GUNDERSON, DS .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1995, 64 (01) :89-100
[9]  
Erdos P., 1962, Illinois J. Math., V6, P122
[10]  
Erdos P., 1955, RIV LEMAT, V9, P13