论文标题
高度连接子图的Ramsey类型问题
A Ramsey Type problem for highly connected subgraphs
论文作者
论文摘要
Bollobás和Gyárfás推测，对于任何$ k，n \ in \ mathbb {z}^+$，带有$ n> 4（k-1）$，每$ n $ dertices上的完整图的每2层色都会导致$ k $ k $连接的单色子副本，并至少与$ n-2k $ n-2k+2k+2k+2k+2k+Vertices。我们找到一个具有$ n = \ lfloor 5k-2.5- \ sqrt {8k- \ frac {31} {4}}} \ rfloor $的反例，从而证明了这一想法，我们显示了结论，我们以$ n> 5k-2.5- \ sqrt} $ n} $ n}} $ n} {41 \ ge 16 $。
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$.
