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(F, x) 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(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 ((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 等数据库收录! |
|