Bollobás and Gyárfás conjectured that for any positive integers k and n, with n > 4(k-1), every 2-edge-coloring of the complete graph on n vertices leads to a k-connected monochromatic subgraph with at least n-2k+2 vertices. In this talk, we will illustrate some counterexamples with n = 5k – O(/sqrt{k}), thus disproving the conjecture. We will also introduce a proof of the conjecture for larger n. This is a joint work with Hehui Wu, and Chunlok Lo.

海报