Degree Ramsey numbers for cycles and blowups of trees

作者：Jiang Tao^*; Milans Kevin G; West Douglas B

来源：European Journal of Combinatorics, 2013, 34(2): 414-423.

DOI：10.1016/j.ejc.2012.08.004

Let H -%26gt;(s) G mean that every s-coloring of E(H) produces a monochromatic copy of G in some color class. Let the s-color degree Ramsey number of a graph G, written R-Delta(G; s), be min{Delta(H): H -%26gt;(s) G}. We prove that the 2-color degree Ramsey number is at most 96 for every even cycle and at most 3458 for every odd cycle. For the general s-color problem on even cycles, we prove R-Delta(C-2m; s) %26lt;= 16s(6) for all m, and R-Delta (C-4; s) %26gt;= 0.007s(14/9). The constant upper bound for R-Delta(C-n; 2) uses blowups of graphs, where the d-blowup of a graph G is the graph G%26apos; obtained by replacing each vertex of G with an independent set of size d and each edge e of G with a copy of the complete bipartite graph K-d.d. We also prove the existence of a function f such that if G%26apos; is the d-blowup of G, then R-Delta(G%26apos;; s) %26lt;= f (R-Delta(G; s), s, d).

• 出版日期2013-2