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  rr and a graph  GG the vertex size-Ramsey number of GG, denoted by Rˆv(G,r), is the least number of edges in a graph HH with the property that any rr-coloring of the vertices of  HH yields a monochromatic copy of  GG. We observe that Ωr(Δn)=Rˆv(G,r)=Or(n2) for any GG of order  nn and maximum degree  ΔΔ, 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ˆv(T,r)=Or(Δ2n) for any tree of order nn and maximum degree ΔΔ, which is only off by a factor of ΔΔ from the best possible.