Monochromatic 4-connected subgraphs in constrained 2-edge-colorings of Kn

Hongping Luo, Yingli Kang, Shili Wen

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.


Full Text: PDF

How to Cite this Article:

Hongping Luo, Yingli Kang, Shili Wen, Monochromatic 4-connected subgraphs in constrained 2-edge-colorings of Kn, Journal of Mathematical and Computational Science, Vol 2, No 2 (2012), 386-393

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.

J. Math. Comput. Sci.

ISSN: 1927-5307

Editorial Office: jmcs@scik.org

 

Copyright ©2019 JMCS