Monochromatic $k$-connected Subgraphs in 2-edge-colored Complete Graphs.
2020
Bollobas and Gyarfas conjectured that for any $k, n \in \mathbb{Z}^+$ 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. We find a counterexample with $n = 5k-2\lceil\sqrt{2k-1}\rceil-3$, thus disproving the conjecture, and we show the conjecture is true for $n \ge 5k-\min\{\sqrt{4k-2}+3, 0.5k+4\}$.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
15
References
0
Citations
NaN
KQI