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

Abstract

The $r$-color size-Ramsey number of a graph $H$, denoted by ${\hat{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 ${\hat{R}}_r(P_{m+1})=\hat{I}\text{c◯}(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 ${\hat{R}}_r(K_{1,m})=r(m-1)+1$. We prove that the star is actually the only exception; that is, ${\hat{R}}_r(H)=\hat{I}\text{c◯}(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 ${\hat{R}}_2(T)=\hat{I}˜({\hat{I}}^2(T))$ for every tree $T$ with bipartition $\{V_1,V_2\}$ and ${\hat{I}}^2(T)=|V_1|\max \{d(v):v\in V_1\}+|V_2|\max \{d(v):v\in V_2\}$. We prove that ${\hat{R}}_r(T)=\hat{I}\text{c◯}(r^2{\hat{I}}^2(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 ${\hat{I}}^2(T)=\hat{I}\text{c◯}(n_1{n}_2)$ (which includes all non-star trees of linear maximum degree and all trees of radius 2 for example) we have ${\hat{R}}_r(T)=\hat{I}˜(r^2{\hat{I}}^2(T))$.

(v3) 16 pages (plus a 2-page appendix), final revisions. In particular, fixed an error in the appendix which significantly changed the statement of Theorem 7.4; (v2) 15 pages (plus a 2-page appendix), many revisions throughout the paper in response to referee reports; (v1) 11 pages (plus a 1-page appendix)