On a Conjecture of Erd\H os on Size Ramsey Number of Star Forests

Abstract

Given graphs $F_1,F_2$ and $G$, we say that $G$ is Ramsey for $(F_1,F_2)$ and we write $G\to (F_1,F_2)$, if for every edge coloring of $G$ by red and blue, there is either a red copy of $F_1$ or a blue copy of $F_2$ in $G$. The size Ramsey number $\hat{r}(F_1,F_2)$ is defined as the minimum number of edges of a graph $G$ such that $G\to (F_1,F_2)$. This paper provides the exact value of $\hat{r}(F_1,F_2)$ for many pairs $(F_1,F_2)$ of star forests, giving a partial solution to a conjecture of Burr et al. (Ramsey-minimal graphs for multiple copies, Indagationes Mathematicae, 81(2) (1978), 187-195).