For every $n\in\mathbb{N}$ and $k\geqslant2$, 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\geqslant3$, it is known that the complete graph can be replaced by a graph $G$ with $\delta(G)\geqslant(1-\varepsilon_k)n$ for some constant $\varepsilon_k$. In this paper, we show that the maximum possible value of $\varepsilon_3$ is $\frac16$. This disproves a conjecture of Gyárfas and Sárközy.
@article{10_37236_9039,
author = {Hannah Guggiari and Alex Scott},
title = {Monochromatic components in edge-coloured graphs with large minimum degree},
journal = {The electronic journal of combinatorics},
year = {2021},
volume = {28},
number = {1},
doi = {10.37236/9039},
zbl = {1456.05063},
url = {http://geodesic.mathdoc.fr/articles/10.37236/9039/}
}
TY - JOUR
AU - Hannah Guggiari
AU - Alex Scott
TI - Monochromatic components in edge-coloured graphs with large minimum degree
JO - The electronic journal of combinatorics
PY - 2021
VL - 28
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/9039/
DO - 10.37236/9039
ID - 10_37236_9039
ER -
%0 Journal Article
%A Hannah Guggiari
%A Alex Scott
%T Monochromatic components in edge-coloured graphs with large minimum degree
%J The electronic journal of combinatorics
%D 2021
%V 28
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/9039/
%R 10.37236/9039
%F 10_37236_9039
Hannah Guggiari; Alex Scott. Monochromatic components in edge-coloured graphs with large minimum degree. The electronic journal of combinatorics, Tome 28 (2021) no. 1. doi: 10.37236/9039
