A Ramsey Type problem for highly connected subgraphs

Abstract

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$.

References in corpus (1)

• Forbidden rainbow subgraphs that force large monochromatic or multicolored k-connected subgraphs

Cited by in corpus (1)

• The power of many colours