Problem Statement
Let $m_1\leq\cdots\leq m_k$ and $n$ be sufficiently large. If $T$ is a tree on $n$ vertices and $G$ is the complete multipartite graph with vertex class sizes $m_1,\ldots,m_k$ then prove that\[R(T,G)\leq (\chi(G)-1)(R(T,K_{m_1,m_2})-1)+m_1.\]
Categories:
Graph Theory Ramsey Theory
Progress
Chvátal [Ch77] proved that $R(T,K_m)=(m-1)(n-1)+1$.This problem is #16 in Ramsey Theory in the graphs problem collection.
Source: erdosproblems.com/550 | Last verified: January 15, 2026