Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4656756 | Journal of Combinatorial Theory, Series B | 2016 | 5 Pages |
Abstract
We show that each 2-edge coloring of the complete graph on n vertices leads to a monochromatic k -connected subgraph on at least n−2(k−1)n−2(k−1) vertices, provided n≥4k−3n≥4k−3. It settles in the affirmative a conjecture of Bollobás and Gyárfás.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Tomasz Łuczak,