Problem #549: If $T$ is a tree which is a bipartite graph with $k$...

---

Progress

This is a special case of a conjecture of Burr [Bu74] (see [547]).

It follows from results in [EFRS82] that $R(T)\geq 4k-1$.

This is false: Norin, Sun, and Zhao [NSZ16] have proved that if $T$ is the union of two stars on $k$ and $2k$ vertices, with an edge joining the centre of the two stars, then $R(T)\geq (4.2-o(1))k$, and conjectured that $R(T)=(4.2+o(1))k$.

The best upper bound for the Ramsey number for this tree is $R(T)\leq (4.21526+o(1))k$, obtained using the flag algebra method by Norin, Sun, and Zhao [NSZ16]. Dubó and Stein [DuSt24] have given a short elementary proof of the weaker bound $R(T)\leq \lceil 4.27492k\rceil+1$

Montgomery, Pavez-Signé, and Yan [MPY25] have proved that $R(T)=4k-1$ if $T$ has maximum degree at most $ck$ for some constant $c>0$.

Erdős, Faudree, Rousseau, and Schelp [EFRS82] proved that $R(T)=4k-1$ if $T$ is a 'broom', formed by identifying the centre of a star on $k+1$ vertices with an endpoint of a path on $2k$ vertices. Burr and Erdős [BuEr76] proved that $R(T)=4k-1$ if $T$ is formed by identifying one end of a path on $4$ vertices with the centre of a star on $k-1$ vertices, and the other endpoint with the centre of a star on $2k-1$ vertices.

This problem is #15 in Ramsey Theory in the graphs problem collection.

See also [547].