科研之友
微信
新浪微博
Facebook
分享链接
摘要
Gyarfas conjectured that for a given forest F, there exists an integer function f(F, x) such that chi(G) <= f(F,omega(G)) for each F-free graph G, where omega(G) is the clique number of G. The broom B(m, n) 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(m, n)-free graph is-colorable as an extension of a result of Randerath and Schiermeyer and a result of Gyarfas, 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 p >= 4 and T not congruent to K-1,K-3 .
