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

The $r$-color size-Ramsey number of a graph $H$, denoted by ${\widehat{R}}_r(H)$, is the minimum 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 ${\widehat{R}}_r(P_{m+1})=\mathrm{\Omega }(r^{2}m)$ where $P_{m+1}$ 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 $\sqrt{m}$. He also notes that some restriction on the vertex cover number is necessary since the star with $m$ edges, $K_{1,m}$, has vertex cover number 1 and satisfies ${\widehat{R}}_r(K_{1,m})=r(m-1)+1$. We prove that the star is actually the only exception; that is, ${\widehat{R}}_r(H)=\mathrm{\Omega }(r^{2}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 ${\widehat{R}}_2(T)=\mathrm{\Theta }(\beta (T))$ for every tree $T$ with bipartition $\{V_1,V_2\}$ and $\beta (T)=\mathrm{\mid }{V}_1\mathrm{\mid }\max \{d(v):v\in V_1\}+\mathrm{\mid }{V}_2\mathrm{\mid }\max \{d(v):v\in V_2\}$. We prove that ${\widehat{R}}_r(T)=\mathrm{\Omega }(r^2\beta (T))$ for every tree $T$, again with the exception of the star. Additionally, we prove that for the family of non-star trees $T$ with $\beta (T)=\mathrm{\Omega }(n_1{n}_2)$ (which includes all non-star trees of linear maximum degree and all trees of radius 2 for example) we have ${\widehat{R}}_r(T)=\mathrm{\Theta }(r^2\beta (T))$.