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

The chromatic number for fork-free graphs

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.