Erdős Problem #557

Let \(R_k(G)\) 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_k(T)\leq kn+O(1)\] for any tree \(T\) on \(n\) vertices? The answer is yes, with an absolute constant: \(R_k(T) \leq kn + 3\) for all \(k\) and \(n\). For \(n \geq 2\) this follows from the explicit bound \(R_k(T) \leq k(n-2)+3\), a consequence of the Erdős–Sós theorem (Erdős problem 548) by the pigeonhole principle, as recorded on the problem page; Reed and Stein [ReSt26] derived that bound for \(n\) large in terms of \(k\) from their dense-graph case of Erdős–Sós. For the one-vertex tree, \(R_k(T) \leq 2\).