OPEN
This is open, and cannot be resolved with a finite computation.
Let $\hat{R}(G)$ denote the size Ramsey number, the minimal number of edges $m$ such that there is a graph $H$ with $m$ edges such that in any $2$-colouring of the edges of $H$ there is a monochromatic copy of $G$.
Let $F_1$ and $F_2$ be the union of stars. More precisely, let $F_1=\cup_{i\leq s} K_{1,n_i}$ and $F_2=\cup_{j\leq t} K_{1,m_j}$. Prove that\[\hat{R}(F_1,F_2) = \sum_{2\leq k\leq s+2}\max\{n_i+m_j-1 : i+j=k\}.\]
Burr, Erdős, Faudree, Rousseau, and Schelp
[BEFRS78] proved this when all the $n_i$ are identical and all the $m_i$ are identical.
See also
the entry in the graphs problem collection.
View the LaTeX source
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #561, https://www.erdosproblems.com/561, accessed 2026-01-16
