The vertex size-Ramsey number

In this paper, we study an analogue of size-Ramsey numbers for vertex colorings. For a given number of colors r and a graph G the vertex size-Ramsey number of G, denoted by (R) over cap (v)(G, r), is the least number of edges in a graph H with the property that any r-coloring of the vertices of H yields a monochromatic copy of G. We observe that Omega(r) (Delta n) = (R) over cap (v)(G, r) = O-r(n(2)) for any G of order n and maximum degree Delta, and prove that for some graphs these bounds are tight. On the other hand, we show that even 3-regular graphs can have nonlinear vertex size-Ramsey numbers. Finally, we prove that (R) over cap (v) (T, r) = O-r(Delta(2)n) for any tree of order n and maximum degree Delta, which is only off by a factor of Delta from the best possible. (C) 2016 Elsevier B.V. All rights reserved.