Bollobás and Gyárfás conjectured that for any $k, n \in \mathbb{Z}^+$ with $n > 4(k-1)$, every 2-edge-coloring of the complete graph on $n$ vertices leads to a $k$-connected monochromatic subgraph with at least $n-2k+2$ vertices. We find a counterexample with $n = \lfloor 5k-2.5-\sqrt{8k-\frac{31}{4}} \rfloor$, thus disproving the conjecture, and we show the conclusion holds for $n > 5k-2.5-\sqrt{8k-\frac{31}{4}}$ when $k \ge 16$.
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。