Highly connected monochromatic subgraphs

Abstract: We conjecture that for every 2-coloring of the edges of the complete graph contains a k-connected monochromatic subgraph with at least vertices. This conjecture, if true, is best possible. Here we prove it for , and show how to reduce it to the case . We prove the following result as well: for every 2-colored contains a k-connected monochromatic subgraph with at least vertices. [Copyright &y& Elsevier]