Some degree Ramsey numbers

Abstract

For graphs H, G1,..., Gs, let H → (G1,..., G.) denote that any edge-coloring of H by colors 1,..., s contains a monochromatic in some color i. We shall write H → (G, ..., G) as H →G in short. Define R{G1,... ,Gs) = min{(H) : H → (G1,...,Gs)}, which is called as the degree Ramsey number. We write Ra(G, ..., G) as Ra(G; s). The open t-blowup of a graph G, denoted by G(t), is obtained by replacing every vertex with an independent set of size t and every edge with a copy of the complete bipartite graph Kt,t We show that R(C2n(t); s) ≤ 16s6m(m t)12, where m is the least integer such that Km,m → Kt,t Let mi be a positive integer and define Ti as a tree with one vertex of degree exactly mi and others of degree at most[mi/2] We prove that BR(T1,... Ts) = ∑s i=i(mi - 1) + 1 and R(T1 ,... ,Ts) ≤2 ∑s i=1)+, where = 1 when all mi are odd or some mi is even and mj = 1(j≠i) and = 0 otherwise. For general trees, R(T1,..., Ts) ≤ 2 ∑s i=1( (Ti) -1). Finally, we show that R (P3,Pn) = 3 for n ≥ 4 and R (Pm,Pn) = 3 for m {4,5} and n {4,5,6}. © 2018 Utilitas Mathematica Publishing Inc. All rights reserved.