Large monochromatic components in edge colored graphs with a minimum degree condition (Q2401439)

Summary: It is well-known that in every \(k\)-coloring of the edges of the complete graph \(K_n\) there is a monochromatic connected component of order at least \(\frac{n}{k-1}\). In this paper we study an extension of this problem by replacing complete graphs by graphs of large minimum degree. For \(k=2\) the authors proved that \(\delta(G)\geq\frac{3n}{4}\) ensures a monochromatic connected component with at least \(\delta(G)+1\) vertices in every \(2\)-coloring of the edges of a graph \(G\) with \(n\) vertices. This result is sharp, thus for \(k=2\) we really need a complete graph to guarantee that one of the colors has a monochromatic connected spanning subgraph. Our main result here is that for larger values of \(k\) the situation is different, graphs of minimum degree \((1-\epsilon_k)n\) can replace complete graphs and still there is a monochromatic connected component of order at least \(\frac{n}{k-1}\), in fact \[ \delta(G)\geq \left(1 - \frac{1}{1000(k-1)^9}\right)n \] suffices.{ }Our second result is an improvement of this bound for \(k=3\). If the edges of \(G\) with \(\delta(G)\geq \frac{9n}{10}\) are \(3\)-colored, then there is a monochromatic component of order at least \(\frac{n}{2}\). We conjecture that this can be improved to \(\frac{7n}{9}\) and for general \(k\) we conjecture the following: if \(k\geq 3\) and \(G\) is a graph of order \(n\) such that \(\delta(G)\geq \left(1-\frac{k-1}{k^2}\right)n\), then in any \(k\)-coloring of the edges of \(G\) there is a monochromatic connected component of order at least \(\frac{n}{k-1}\).