Degree Ramsey numbers for even cycles

被引:4
作者
Tait, Michael [1 ]
机构
[1] Carnegie Mellon Univ, Dept Math Sci, Pittsburgh, PA 15213 USA
基金
美国国家科学基金会;
关键词
Ramsey number; Degree Ramsey number; Even cycle; Generalized polygon; BOUNDED DEGREE; GRAPHS; SIZE; TREES; SUBGRAPHS;
D O I
10.1016/j.disc.2017.08.016
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Let H -> G denote that any s-coloring of E(H) contains a monochromatic G. The degree Ramsey number of a graph G, denoted by R Delta(G, s), is min{Delta(H) : H -> G}. We consider degree Ramsey numbers where G is a fixed even cycle. Kinnersley, Milans, and West showed that R-Delta(C-2k, s) >= 2s, and Kang and Perarnau showed that R-Delta(C-4, s) = Theta(s(2)). Our main result is that R-Delta(C-6, s) = Theta(S-3/2) and R-Delta(C-10, s) = Theta(S-5/4). Additionally, we substantially improve the lower bound for R-Delta(C-2k, s) for general k. (C) 2017 Elsevier B.V. All rights reserved.
引用
收藏
页码:104 / 108
页数:5
相关论文
共 29 条