华东师范大学学报（自然科学版） >

2016 , Vol. 2016 >Issue 1: 102 - 106

DOI: https://doi.org/10.3969/j.issn.1000-5641.2016.01.005

应用数学与基础数学

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

  • 王晓
展开
  • 商洛学院~~数学与计算机应用学院, 陕西~商洛 726000
王晓, 男, 硕士, 讲师,研究方向为图论及其应用.

收稿日期: 2014-10-29

  网络出版日期: 2016-03-10

基金资助

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

收起

The chromatic number for fork-free graphs

  • WANG Xiao
Expand

Received date: 2014-10-29

  Online published: 2016-03-10

Fold

摘要

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

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

本文引用格式

王晓 . 不含叉形图为导出子图的图的色数~(英)[J]. 华东师范大学学报（自然科学版）, 2016 , 2016(1) : 102 -106 . DOI: 10.3969/j.issn.1000-5641.2016.01.005

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

参考文献

[1]REINHARD D. Graph Theorey (Second Edition) [M]. Hong Kong:Springer-Verlag, 2000: 95-117.
[2]GY\'{A]RF\'{A]S A. Problems from the world surrounding perfect graphs [J]. Zastow Mat, 1987, 19: 413-441.
[3]WAGON S. A bound on the chromatic number of graphs without certain induced subgraphs [J]. J of Combin Theory, Series B, 1980, 29(3):345-346.
[4]GY\'{A]RF\'{A]S A, SZEMER\'{E]DI E and Tuza. Induced subtrees ingraphs of large chromatic number [J]. Discrete Math, 1980, 30(3):235-244.
[5] DUAN F and WU B Y. On chromatic number of graphs without certain induced subgraph [J]. Ars combinatoria, 2011, 101: 33-34.
[6] DUAN F and ZHANG W J. On chromatic number of $\{2K_1+K_2, C_4\]$-free graphs [J]. Journal of East China Normal University: Natural Science, 2014(1): 9-12.
[7] RANDERATH B, SCHIERMEYER I.  A note on Brooks' theorem for triangle-free graphs [J]. Australas J Comb, 2002, 26: 3-9.
[8] RANDERATH B, SCHIERMEYER I. Vertex coloring and forbidden subgraphs-a survey [J]. Graphs Combin, 2004, 20(1): 1-40.
[9] RANDERATH B. The Vizing bound for the chromatic number based on forbidden pairs [D]. Nordrhein-Westfalen: RWTH Aachen University, 1998.
[10] FAN G, XU B, YE T, et al. Forbidden subgraphs and 3-colorings [J]. Siam J Disc Math, 2014, 28: 1226-1256.
Options
文章导航

/

〈 〉