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 条
  • [1] Norm-graphs:: Variations and applications
    Alon, N
    Rónyai, L
    Szabó, T
    [J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 1999, 76 (02) : 280 - 290
  • [2] Alon N., 2016, The Probabilistic Method, Vfourth
  • [3] ON SIZE RAMSEY NUMBER OF PATHS, TREES, AND CIRCUITS .1.
    BECK, J
    [J]. JOURNAL OF GRAPH THEORY, 1983, 7 (01) : 115 - 129
  • [4] Beck Jozsef, 1983, ALGORITHMS COMBIN, V5, P34
  • [5] Bondy J. A., 1974, Journal of Combinatorial Theory, Series B, V16, P97, DOI 10.1016/0095-8956(74)90052-5
  • [6] Bukh Boris, 2014, ARXIV14031601
  • [7] BURR S. A., 1976, Ars Combin., V1, P167
  • [8] Conlon D, 2015, Surveys in combinatorics, V2015, P49
  • [9] The size-Ramsey number of trees
    Dellamonica, Domingos, Jr.
    [J]. RANDOM STRUCTURES & ALGORITHMS, 2012, 40 (01) : 49 - 73
  • [10] A note on the size-Ramsey number of long subdivisions of graphs
    Donadelli, J
    Haxell, PE
    Kohayakawa, Y
    [J]. RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS, 2005, 39 (01): : 191 - 206