Upper bounds on the chromatic number of triangle-free graphs with a forbidden subtree

Gyárfás conjectured that for a given forest F, there exists an integer function f(F, x) such that $$\chi (G)\le f(F,\omega (G))$$ χ ( G ) ≤ f ( F , ω ( G ) ) for each F-free graph G, where $$\omega (G)$$ ω ( G ) is the clique number of G. The broom B(m, n) is the tree of order $$m+n$$ m + n obtained from identifying a vertex of degree 1 of the path $$P_m$$ P m with the center of the star $$K_{1,n}$$ K 1 , n . In this note, we prove that every connected, triangle-free and B(m, n)-free graph is $$(m+n-2)$$ ( 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$$ C 4 -free and T-free graph is $$(p-2)$$ ( p - 2 ) -colorable, where T is a tree of order $$p\ge 4$$ p ≥ 4 and $$T\not \cong K_{1,3}$$ T ≇ K 1 , 3 .