首页 | 本学科首页   官方微博 | 高级检索  
     


Upper bounds on the chromatic number of triangle-free graphs with a forbidden subtree
Authors:Xiao Wang  Baoyindureng Wu
Affiliation:1.College of Mathematics and Computer Application,Shangluo University,Shangluo,People’s Republic of China;2.College of Mathematics and System Sciences,Xinjiang University,Urumqi,People’s Republic of China
Abstract:Gyárfás conjectured that for a given forest F, there exists an integer function f(Fx) such that (chi (G)le f(F,omega (G))) for each F-free graph G, where (omega (G)) is the clique number of G. The broom B(mn) is the tree of order (m+n) obtained from identifying a vertex of degree 1 of the path (P_m) with the center of the star (K_{1,n}). In this note, we prove that every connected, triangle-free and B(mn)-free graph is ((m+n-2))-colorable as an extension of a result of Randerath and Schiermeyer and a result of Gyárfás, Szemeredi and Tuza. In addition, it is also shown that every connected, triangle-free, (C_4)-free and T-free graph is ((p-2))-colorable, where T is a tree of order (pge 4) and (Tnot cong K_{1,3}).
Keywords:
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号