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

作者：王晓

来源：华东师范大学学报(自然科学版), 2016, (01): 102-106.

• 色数
• 不含三角形
• 不含叉形图

Randerath曾猜想每一个不含三角形和不含叉形图为导出子图的图是3-可着色的.通过一个引理,证明了该猜想在没有长为4的圈的图类上是成立的.进而,还证明了每一个不含三角形、不含C4并且不含C2,2,1,n作为导出子图的图是(n+2)-可着色的,这里C2,2,1,n表示将图E的中心点和路Pn的一个端点连接而得到的阶为(n+6)的长把叉形图.

• 单位
  商洛学院