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.
Copyright © 2012 Hongping Luo, Yingli Kang, Shili Wen. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Cite this article
H. Luo, Y. Kang, S. Wen, Monochromatic 4-connected subgraphs in constrained 2-edge-colorings of Kn, J. Math. Comput. Sci. 2 (2012), 386–393.
BibTeX
@article{Luo2012,
author = {Luo, Hongping and Kang, Yingli and Wen, Shili},
title = {Monochromatic 4-connected subgraphs in constrained 2-edge-colorings of Kn},
journal = {J. Math. Comput. Sci.},
volume = {2},
year = {2012},
pages = {386--393},
doi = {}
}