Monochromatic 4-connected subgraphs in constrained 2-edge-colorings of Kn

Abstract

Bollobas and Gyarfas conjectured that for n >= 4k-3 every 2-edge-coloring of Kn contains a monochromatic k-connected subgraph with at least n -2k + 2 vertices. It was proved that the conjecture holds for k = 2,3. In this paper, we prove t at if each monochro- matic k-connected (k = 2; 3) subgraph has at most n¡2k +2 vertices in 2-edge-colored Kn (n >=13), then there exists a monochromatic 4-connecte subgraph with at least n - 6 vertices.