A note on the multicolor size-Ramsey numbers of connected graphs

The r-color size-Ramsey number of a graph H, denoted R̂ᵣ(H) is the smallest number of edges in a graph G having the property that every r-coloring of the edges of G contains a monochromatic copy of H. Krivelevich proved that R̂ᵣ(Pₘ₊₁)=Ω(r²m) where Pₘ₊₁ is the path on m edges. He explains that his proof actually applies to any connected graph H with m edges and vertex cover number larger than √m. He also notes that some restriction on the vertex cover number is necessary since the star with m edges, K1,m, has vertex cover number 1 and satisfies R̂ᵣ(K1,m)=r(m-1)+1. We prove that the star is actually the only exception; that is, R̂ᵣ(H)=Ω(r²m) for every non-star connected graph H with m edges. We also prove a strengthening of this result for trees. It follows from results of Beck and Dellamonica that R̂₂(T)=Θ(β(T)) for every tree T with bipartition ₁, V₂\ and β(T)=|V₁|max(v):v∈ V₁\+|V₂|max(v):v∈ V₂\. We prove that R̂ᵣ(T)=Ω(r²β(T)) for every tree T, again with the exception of the star. Additionally, we prove that for a certain class of trees T (which includes all trees of radius 2 and all non-star trees with linear maximum degree) we have R̂ᵣ(T)=Θ(r²β(T)) for all T∈ T.