A Ramsey Type problem for highly connected subgraphs

Abstract: Bollob'{a}s and Gy'{a}rf'{a}s conjectured that for any

k, n i n m a t h b b 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 - 2 k + 2

vertices. We find a counterexample with

n = l f l o o r 5 k - 2.5 - s q r t 8 k - f r a c 314 f l o o r

, thus disproving the conjecture, and we show the conclusion holds for

n > 5 k - 2.5 - s q r t 8 k - f r a c 314

when

k g e 16

.

This page was built for publication: A Ramsey Type problem for highly connected subgraphs