Monochromatic Components in Edge-Coloured Graphs with Large Minimum Degree

Abstract

For every $n\in \mathbb{N}$ and $k\ge 2$, it is known that every $k$-edge-colouring of the complete graph on $n$ vertices contains a monochromatic connected component of order at least $\frac{n}{k-1}$. For $k\ge 3$, it is known that the complete graph can be replaced by a graph $G$ with $\hat{I}´(G)\ge (1-{\epsilon }_k)n$ for some constant ${\epsilon }_k$. In this paper, we show that the maximum possible value of ${\epsilon }_3$ is $\frac{1}{6}$. This disproves a conjecture of Gyárfas and Sárközy.

18 pages, 6 figures