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, K₁, ₌, has vertex cover number 1 and satisfies Rᵣ (K₁, ₌) =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₁, V₂\ and (T) =|V₁|\d (v): v V₁\+|V₂|\d (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.