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

王晓

doi:10.3969/j.issn.1000-5641.2016.01.0051

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名

邮箱

手机号码

标题

留言内容

验证码

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

doi: 10.3969/j.issn.1000-5641.2016.01.0051

王晓^,

1.
商洛学院~~数学与计算机应用学院, 陕西~商洛 726000

基金项目:

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

详细信息

作者简介:
王晓, 男, 硕士, 讲师,研究方向为图论及其应用.

通讯作者:
王晓, 男, 硕士, 讲师,研究方向为图论及其应用.

中图分类号: O175.5
计量
- 文章访问数: 628
- HTML全文浏览量: 21
- PDF下载量: 976
- 被引次数: 0
出版历程
- 收稿日期: 2014-10-29
- 刊出日期: 2016-01-25

The chromatic number for fork-free graphs

WANG Xiao^,

摘要

摘要: 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.
- chromatic number triangle-freefork-free /

HTML全文

参考文献(1)

[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.

施引文献

资源附件(0)

访问统计