Note on Highly Connected Monochromatic Subgraphs in $2$-Colored Complete Graphs

Shinya Fujita, Colton Magnant

Abstract


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 $n\ge 6.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.


Full Text: PDF