Large monochromatic components in almost complete graphs and bipartite graphs (Q2034067)

Summary: \textit{A. Gyárfas} [``Partition coverings and blocking sets in hypergraphs'', Commun. Comput. Autom. Inst. Hungar. Acad. Sci. 71 (1977)] 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, \textit{A. Gyárfás} and \textit{G. N. Sárközy} [Comb. Probab. Comput. 21, No. 1--2, 179--186 (2012; Zbl 1241.05091)] 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 a result of \textit{L. Debiasio} et al. [J. Graph Theory 94, No. 1, 117--130 (2020; Zbl 1495.05090)].