The Gárfás–Sumner conjecture asks whether for every tree T , the class of (induced) T -free graphs is $$\chi $$ χ -bounded. The conjecture is solved for several special trees,… Click to show full abstract
The Gárfás–Sumner conjecture asks whether for every tree T , the class of (induced) T -free graphs is $$\chi $$ χ -bounded. The conjecture is solved for several special trees, but it is still open in general. Motivated by the conjecture, the chromatic number of triangle-free and broom-free graphs is well studied, since a broom is one of the generalizations of a star, where a broom B ( m , n ) is the graph obtained from a star $$K_{1,n}$$ K 1 , n and an m -vertex path $$P_m$$ P m by identifying the center of $$K_{1,n}$$ K 1 , n and a leaf of $$P_m$$ P m . Gárfás, Szemeredi and Tuza proved that for every triangle-free and B ( m , n )-free graph G , $$\chi (G) \le m+n-1$$ χ ( G ) ≤ m + n - 1 . This upper bound has been improved by Wang and Wu to $$m+n-2$$ m + n - 2 for $$m\ge 2, n\ge 1$$ m ≥ 2 , n ≥ 1 . In this paper, we prove that any triangle-free and B (4, 2)-free graph G is 3-colorable if the number of vertices of G is at least 17. Furthermore, the above estimation is the best possible since there exists a triangle-free and B (4, 2)-free 4-chromatic graph with sixteen vertices, named the Clebsch graph.
               
Click one of the above tabs to view related content.