论文标题
几乎完整的图和两部分图中的大型单色组件
Large monochromatic components in almost complete graphs and bipartite graphs
论文作者
论文摘要
Gyárfas证明，$ k_n $的每种着色$ t+1 $颜色包含一个至少$ n/t $的单色连接组件。 Later, Gyárfás and Sárközy asked for which values of $γ=γ(t)$ does the following strengthening for almost complete graphs hold: if $G$ is an $n$-vertex graph with minimum degree at least $(1-γ)n$, then every $(t+1)$-edge coloring of $G$ contains a monochromatic component of size at least $n/t$.我们显示$γ= 1/（6t^3）$就足够了，可以改善Debiasio，Krueger和Sárközy的结果。
Gyárfas 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, Gyárfás and Sárközy asked for which values of $γ=γ(t)$ does the following strengthening for almost complete graphs hold: if $G$ is an $n$-vertex graph with minimum degree at least $(1-γ)n$, then every $(t+1)$-edge coloring of $G$ contains a monochromatic component of size at least $n/t$. We show $γ= 1/(6t^3)$ suffices, improving a result of DeBiasio, Krueger, and Sárközy.
