Gallai-Ramsey numbers of C10 and C12

被引:0
作者
Lei, Hui [1 ,2 ]
Shi, Yongtang [3 ,4 ]
Song, Zi-Xia [5 ]
Zhang, Jingmei [5 ]
机构
[1] Nankai Univ, LPMC, Sch Stat & Data Sci, Tianjin 300071, Peoples R China
[2] Nankai Univ, KLMDASR, Tianjin 300071, Peoples R China
[3] Nankai Univ, Ctr Combinator, Tianjin 300071, Peoples R China
[4] Nankai Univ, LPMC, Tianjin 300071, Peoples R China
[5] Univ Cent Florida, Dept Math, Orlando, FL 32816 USA
来源
AUSTRALASIAN JOURNAL OF COMBINATORICS | 2021年 / 79卷
基金
中国国家自然科学基金;
关键词
COMPLETE GRAPHS; CONJECTURE;
D O I
暂无
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
A Gallai coloring is a coloring of the edges of a complete graph without rainbow triangles, and a Gallai k-coloring is a Gallai coloring that uses at most k colors. Given an integer k >= 1 and graphs H-1,..., H-k, the GallaiRamsey number GR(H-1,..., H-k) is the least integer n such that every Gallai k-coloring of the complete graph K-n contains a monochromatic copy of Hi in color i for some i is an element of{1,..., k}. When H = H-1 = . . . = H-k, we simply write GR(k)(H). We continue to study Gallai-Ramsey numbers of even cycles and paths. For all n >= 3 and k = 1, let G(i) = P2i+ 3 be a path on 2i + 3 vertices for all i is an element of {0, 1,..., n - 2} and G(n-1). {C-2n, P2n+ 1}. Let i(j) is an element of {0, 1,..., n - 1} for all j is an element of {1,..., k} with i(1) >= i(2) >= . . . >= i(k). Song recently conjectured that GR(Gi(1),..., Gi(k)) = vertical bar G(i1)vertical bar + Sigma(k)(j=2) i(j). This conjecture has been verified to be true for n is an element of {3, 4} and all k = 1. In this paper, we prove that the aforementioned conjecture holds for n is an element of{5, 6} and all k = 1. Our result implies that for all k >= 1, GR(k)(C-2n) = GR(k)(P-2n) = (n- 1)k+ n+ 1 for n is an element of {5, 6} and GR(k)(P2n+1) = (n- 1)k+ n + 2 for 1 <= n <= 6.
引用
收藏
页码:380 / 400
页数:21
相关论文
共 24 条
[1]   R(5,5) ≤ 48 [J].
Angeltveit, Vigleik ;
McKay, Brendan D. .
JOURNAL OF GRAPH THEORY, 2018, 89 (01) :5-13
[2]  
Bosse C., ARXIV180206503
[3]  
Bosse C., ARXIV180809963
[4]   Gallai-Ramsey numbers of C7 with multiple colors [J].
Bruce, Dylan ;
Song, Zi-Xia .
DISCRETE MATHEMATICS, 2019, 342 (04) :1191-1194
[5]  
Cameron K., 1986, Periodica Mathematica Hungarica, V17, P173, DOI 10.1007/BF01848646
[6]   EDGE-COLORED COMPLETE GRAPHS WITH PRECISELY COLORED SUBGRAPHS [J].
CHUNG, FRK ;
GRAHAM, RL .
COMBINATORICA, 1983, 3 (3-4) :315-324
[7]  
Dzido T, 2005, ELECTRON J COMB, V12
[8]  
Faudree R. J., 1974, Discrete Mathematics, V10, P269, DOI 10.1016/0012-365X(74)90122-8
[9]   The Erdos-Hajnal conjecture for rainbow triangles [J].
Fox, Jacob ;
Grinshpun, Andrey ;
Pach, Janos .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2015, 111 :75-125
[10]   Gallai-Ramsey numbers for cycles [J].
Fujita, Shinya ;
Magnant, Colton .
DISCRETE MATHEMATICS, 2011, 311 (13) :1247-1254