华东师范大学学报(自然科学版) ›› 2016, Vol. 2016 ›› Issue (1): 102-106.doi: 10.3969/j.issn.1000-5641.2016.01.005

• 应用数学与基础数学 • 上一篇    下一篇

不含叉形图为导出子图的图的色数~(英)

王晓   

  1. 商洛学院~~数学与计算机应用学院, 陕西~商洛 726000
  • 收稿日期:2014-10-29 出版日期:2016-01-25 发布日期:2016-03-10
  • 通讯作者: 王晓, 男, 硕士, 讲师,研究方向为图论及其应用. E-mail:wangxiaomath@163.com.
  • 作者简介:王晓, 男, 硕士, 讲师,研究方向为图论及其应用.
  • 基金资助:

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

The chromatic number for fork-free graphs

 WANG  Xiao   

  • Received:2014-10-29 Online:2016-01-25 Published:2016-03-10

RichHTML

10

PDF

1194

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

关键词: 色数, 不含三角形;不含叉形图

Abstract: Randerath once conjectured that every triangle-free and fork-free graph is 3-colourable. By a lemma, the conjecture for C_4-free graphs was proved.Moreover, the result that every triangle-free, C_4-free and C_{2,2,1,n}-free graph is (n+2)-colourable was proved as well, where C_{2,2,1,n} is the long handled fork with order (n+6) obtained from E-graph and P_n by joining the center vertex of E and one endvertex of P_n.

Key words: chromatic number, triangle-free;fork-free

中图分类号: