A Note on the Multicolor Size-Ramsey Numbers of Connected Graphs

Abstract

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 (2019) proved that $\widehat{R}_r(P_{m+1})=\Omega(r^2m)$ 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)=\Omega(r^2m)$ 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 (1990) and Dellamonica (2012) that $\widehat{R}_2(T)=\Theta(\beta(T))$ for every tree $T$ with bipartition $\{V_1, V_2\}$ and $\beta(T)=|V_1|\max\{d(v):v\in V_1\}+|V_2|\max\{d(v):v\in V_2\}$. We prove that $\widehat{R}_r(T)=\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)=\Omega(n_1n_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)=\Theta(r^2\beta(T))$.