Size of monochromatic double stars in edge colorings (Q1015436)

It is well-known that there is a monochromatic spanning tree for every 2-coloring of the edges of a complete graph. An earlier result of the first author is the following theorem: If the edges of a complete graph \(K_n\) on \(n\) vertices are coloured with \(r\) colours, then there is a monochromatic subtree with at least \(\frac{n}{r-1}\) vertices. In the present paper, the authors show that for every \(r\)-colouring of the edges of \(K_n\) there is a monochromatic double star with at least \(\frac{n(r+1)+r-1}{r^2}\) vertices. Its is shown that this result is sharp in asymptotic for \(r= 2\). For \(r\geq 3\) it improves a known bound for the largest monochromatic subgraph of diameter at most 3. When \(r\)-colorings are replaced by local \(r\)-colorings, the bound is \(\frac{n(r+1)+r-1}{r^2+ 1}\).