Highly connected monochromatic subgraphs (Q2477397): Difference between revisions

Any 2-coloring of the edges of the complete graph on \(n\) vertices contains a monochromatic spanning tree, as was observed by Erdös a long time ago. Here the authors look for large monochromatic subgraphs of high vertex connectivity in an edge-2-colored \(K_n\). A large family, \(B(n,k)\), of edge-2-colored graphs on \(n\) vertices with the property that the maximal order of a \(k\)-connected monochromatic subgraph is \(n-2(k-1)\) is constructed. The authors conjecture that for \(n>4(k-1)\) every 2-colored \(K_n\) contains a \(k\)-connected monochromatic subgraph on at least \(n-2(k-1)\) vertices. If the conjecture is true, the family \(B(n,k)\) shows that it is best possible. The conjecture is proven for \( k=2 \).