Logo
All Random Solved Random Open
SOLVED
If $T$ is a tree which is a bipartite graph with $k$ vertices and $2k$ vertices in the other class then show that $R(T)=4k$.
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$. The best upper bound for the Ramsey number for this tree is $R(T)\leq 4.27492k+1$, obtained by Dubó and Stein [DuSt24].

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

Additional thanks to: Zach Hunter