Problem Statement
Let $R(G;k)$ denote the minimal $m$ such that if the edges of $K_m$ are $k$-coloured then there is a monochromatic copy of $G$. Is it true that\[R(T;k)\leq kn+O(1)\]for any tree $T$ on $n$ vertices?
Categories:
Graph Theory Ramsey Theory
Progress
A problem of Erdős and Graham. Implied by [548].This would be best possible since, for example, $R(S_n,k)\geq kn-O(k)$ if $S_n=K_{1,n-1}$ is a star on $n$ vertices.
This problem is #26 in Ramsey Theory in the graphs problem collection.
Source: erdosproblems.com/557 | Last verified: January 15, 2026