Note on 2-edge-colorings of complete graphs with small monochromatic k-connected subgraphs  

作　　者：JIN Ze-min WANG Yu-ling WEN Shi-li 

机构地区：[1]Department of Mathematics, Zhejiang Normal University

出　　处：《Applied Mathematics(A Journal of Chinese Universities)》2014年第2期249-252,共4页高校应用数学学报（英文版）（B辑）

基　　金：Supported by the National Natural Science Foundation of China(10701065 and 11101378);Zhejiang Provincial Natural Science Foundation(LY14A010009)

摘　　要：Bollobas and Gyarfas conjectured that for n 〉 4（k - 1） every 2-edge-coloring of Kn contains a monochromatic k-connected subgraph with at least n - 2k ＋ 2 vertices. Liu, et al. proved that the conjecture holds when n 〉 13k - 15. In this note, we characterize all the 2-edge-colorings of Kn where each monochromatic k-connected subgraph has at most n - 2k ＋ 2 vertices for n ≥ 13k - 15.Bollobas and Gyarfas conjectured that for n 〉 4（k - 1） every 2-edge-coloring of Kn contains a monochromatic k-connected subgraph with at least n - 2k ＋ 2 vertices. Liu, et al. proved that the conjecture holds when n 〉 13k - 15. In this note, we characterize all the 2-edge-colorings of Kn where each monochromatic k-connected subgraph has at most n - 2k ＋ 2 vertices for n ≥ 13k - 15.

关 键 词：monochromatic subgraph k-connected subgraph 2-edge-coloring. 

分 类 号：O157.5[理学—数学] TS803[理学—基础数学]