不含叉形图为导出子图的图的色数（英文）  

The chromatic number for fork-free graphs

作　　者：王晓[1] 

机构地区：[1]商洛学院数学与计算机应用学院,陕西商洛726000

出　　处：《华东师范大学学报（自然科学版）》2016年第1期102-106,共5页Journal of East China Normal University(Natural Science)

基　　金：陕西省教育厅自然科学专项基金(12JK089);商洛学院科研基金(12SKY011)

摘　　要：Randerath曾猜想每一个不含三角形和不含叉形图为导出子图的图是3-可着色的.通过一个引理,证明了该猜想在没有长为4的圈的图类上是成立的.进而,还证明了每一个不含三角形、不含C_4并且不含C_(2,2,1,n)作为导出子图的图是(n+2)-可着色的,这里C_(2,2,1,n)表示将图E的中心点和路P_n的一个端点连接而得到的阶为(n+6)的长把叉形图.Randerath once conjectured that every triangle-free and fork-free graph is 3-colourable.By a lemma,the conjecture for C4-free graphs was proved.Moreover,the result that every triangle-free,C4-free and C2,2,1,n-free graph is（n ＋ 2）-colourable was proved as well,where C2,2,1,n is the long handled fork with order（n ＋ 6） obtained from E-graph and Pn by joining the center vertex of E and one endvertex of Pn.

关 键 词：色数 不含三角形 不含叉形图 

分 类 号：O175.5[理学—数学]