Gallai-Ramsey number of even cycles with chords
Gallai-Ramsey number of even cycles with chords
复制标题
加莱-拉姆齐和弦的偶数循环数
DOI：
10.1016/j.disc.2021.112738
复制
发表时间：
2022-03
影响因子：
0.8
通讯作者：
Chen Yaojun
中科院分区：
文献类型：
--
作者：
Zhang Fangfang;Song Zi-Xia;Chen Yaojun
对于图H和整数k≥ 1，k-色Ramsey数Rk（H）是使得完全图KN的边的每一个k-着色都包含H的单色副本的最小整数N.设Cm表示m≥ 4个顶点上的圈，θ m表示由Cm通过添加连接两个不连续顶点的附加边而得到的图族.与奇圈的Ramsey数不同，关于Rk（C2 n）的一般性态知之甚少，只知道对所有k≥ 2和n≥ 2，Rk（C2 n）≥（n− 1）k+ n+ k− 1。本文研究了具有弦的偶数圈在Gallai染色下的Ramsey数，其中Gallai染色是指不含彩虹三角形的完全图的边的染色。对于整数k≥ 1，图H的Gallai-Ramsey数GRk（H）是使得完全图KN的每一个Gallaik-染色都包含H的单色副本的最小正整数N.我们证明了当k≥ 2，n≥ 3时，GRk（Θ 2 n）=（n− 1）k+ n+ 1.这意味着G R k（C 2 n）=（n− 1）k+ n+ 1所有k≥ 2且n≥ 3。我们的结果给出了至少四个顶点上的所有偶数圈的Gallai-Ramsey数的统一证明。
For a graph H and an integer k≥ 1, the k-color Ramsey number R k (H) is the least integer N such that every k-coloring of the edges of the complete graph K N contains a monochromatic copy of H. Let C m denote the cycle on m≥ 4 vertices and let Θ m denote the family of graphs obtained from C m by adding an additional edge joining two non-consecutive vertices. Unlike Ramsey number of odd cycles, little is known about the general behavior of R k (C 2 n) except that R k (C 2 n)≥(n− 1) k+ n+ k− 1 for all k≥ 2 and n≥ 2. In this paper, we study Ramsey number of even cycles with chords under Gallai colorings, where a Gallai coloring is a coloring of the edges of a complete graph without rainbow triangles. For an integer k≥ 1, the Gallai-Ramsey number G R k (H) of a graph H is the least positive integer N such that every Gallai k-coloring of the complete graph K N contains a monochromatic copy of H. We prove that G R k (Θ 2 n)=(n− 1) k+ n+ 1 for all k≥ 2 and n≥ 3. This implies that G R k (C 2 n)=(n− 1) k+ n+ 1 all k≥ 2 and n≥ 3. Our result yields a unified proof for the Gallai-Ramsey number of all even cycles on at least four vertices.
登录
查看更多内容
DOI：
10.1016/j.jctb.2014.09.005
发表时间：
2013-03
期刊：
J. Comb. Theory B
影响因子：
--
作者：
J. Fox;A. Grinshpun;J. Pach
通讯作者：
J. Fox;A. Grinshpun;J. Pach
影响因子：
0.9
作者：
Henry Liu;Colton Magnant;Akira Saito;I. Schiermeyer;Yongtang Shi
通讯作者：
Henry Liu;Colton Magnant;Akira Saito;I. Schiermeyer;Yongtang Shi
影响因子：
1.1
作者：
J. Körner;G. Simonyi
通讯作者：
J. Körner;G. Simonyi
DOI：
10.1090/s0002-9904-1971-12832-x
发表时间：
1971-11
影响因子：
1.3
作者：
G. Chartrand;S. Schuster
通讯作者：
G. Chartrand;S. Schuster
DOI：
10.37236/1980
发表时间：
2005-08
期刊：
Electron. J. Comb.
影响因子：
--
作者：
Tomasz Dzido;A. Nowik;P. Szuca
通讯作者：
Tomasz Dzido;A. Nowik;P. Szuca