Partitioning by monochromatic trees (Q1125948)

Any \(r\)-edge-coloured \(n\)-vertex complete graph \(K^n\) contains at most \(r\) monochromatic trees, all of different colours, whose vertex sets partition the vertex set of \(K^n\), provided \(n\geq 3r^4r!(1-1/r)^{3(1-r)}\log r\). This comes close to proving, for large \(n\), a conjecture of \textit{P. Erdös}, \textit{A. Gyárfás} and \textit{L. Pyber} [J. Comb. Theory, Ser. B 51, No. 1, 90-95 (1991; Zbl 0766.05062)], which states that \(r-1\) trees suffice for all \(n\).