Zoltán Füredi: Monochromatic components in almost complete graphs

Abstract. Gyarfas proved that every coloring of the edges of K_n with  t+1
colors contains a monochromatic connected component of size at least
n/t. Later, Gyarfas and Sarkozy asked for which values of
\gamma=\gamma(t)  does the following strengthening for {almost}
complete graphs hold: if G is an n-vertex graph with minimum degree at
least  (1-\gamma)n, then every (t+1)-edge coloring of  G  contains a
monochromatic component of size at least  n/t. We show  \gamma=
1/(6t^3)  suffices, improving the results of DeBiasio, Krueger, and
Sarkozy as well.

We also point out connections to (t+1)-partite hypergraphs, and
regular intersecting families.

The new results are joint with Ruth Luo.