Note on Highly Connected Monochromatic Subgraphs in 2-Colored Complete Graphs - Fujita, Shinya; Magnant, Colton (The Electronic Journal of Combinatorics, 2011)
In this note, we improve upon some recent results concerning the existence of large monochromatic, highly connected subgraphs in a 2-coloring of a complete graph. In particular, we show that if n6.5(k - 1), then in any 2-coloring of the edges of K_n, there exists a monochromatic k-connected subgraph of order at least n - 2(k - 1). Our result improves upon several recent results by a variety of authors.