The chromatic number of triangle-free and broom-free graphs in terms of the number of vertices
Tóm tắt
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}$$
and an m-vertex path
$$P_m$$
by identifying the center of
$$K_{1,n}$$
and a leaf of
$$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$$
. This upper bound has been improved by Wang and Wu to
$$m+n-2$$
for
$$m\ge 2, n\ge 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.
Tài liệu tham khảo
Brooks, R.L.: On colouring the nodes of network. Math. Proc. Camb. Philos. Soc. 37, 194–197 (1941)
Bryant, V.: A characterisation of some 2-connected graphs and a comment on an algorithmic proof of Brooks’ theorem. Discrete Math. 158, 279–281 (1996)
Diestel, R.: Graph Theory. Graduate Texts in Mathematics, vol. 173, 5th edn. Springer, Berlin (2017)
Erdös, P.: Graph theory and probability. Can. J. Math. 11, 34–38 (1959)
Erdös, P., Hajnal, A.: On chromatic number of graphs and set-systems. Acta Math. Acad. Sci. Hung. 17, 61–99 (1966)
Gyárfás, A.: Problems from the world surrounding perfect graphs. Zastosow. Mat. Appl. Math. 19, 413–441 (1987)
Gyárfás, A., Szemeredi, E., Tuza, Z.: Induced subtrees in graphs of large chromatic number. Discrete Math. 30, 235–244 (1980)
Jensen, T.R., Toft, B.: Graph Coloring Problems. Wiley, New York (1995)
Kierstead, H.A., Penrice, S.G.: Radius two trees specify \(\chi \)-bounded classes. J. Graph Theory 18, 119–129 (1994)
Kohl, A., Schiermeyer, I.: Some results on Reed’s conjecture about \(\omega,\,\Delta \) and \(\chi \) with respect to \(\alpha \). Discrete Math. 310, 1429–1438 (2010)
Randerath, B.: 3-Colorability and forbidden subgraphs. I: characterizing pairs. Discrete Math. 276, 313–325 (2004)
Randerath, B., Schiermeyer, I., Tewes, M.: Three-colourability and forbidden subgraphs. II: polynomial algorithms. Discrete Math. 251, 137–153 (2002)
Randerath, B., Schiermeyer, I.: A note on Brooks’ theorem for triangle-free graphs. Australas. J. Comb. 26, 3–9 (2002)
Randerath, B., Schiermeyer, I.: On Reed’s conjecture about \(\omega,\,\Delta \) and \(\chi \). In: Bondy, A., Fonlupt, J., Fouquet, J.L., Fournier, J.C., Ramirez Alfonsin, J.L. (eds.) Graph Theory in Paris (Proceedings of a Conference in Memory of Claude Berge). Trends in Mathematics, pp. 339–346. Springer, Berlin (2006)
Randerath, B., Schiermeyer, I.: Vertex coloring and forbidden subgraphs, a survey. Graphs Combin. 20, 1–40 (2004)
Reed, B.: \(\omega,\,\Delta \) and \(\chi \). J. Graph Theory 27, 177–212 (1998)
Schiermeyer, I., Randerath, B.: Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey. Graphs Comb. 35, 1–31 (2019)
Sumner, D.P.: Subtrees of a Graph and the Chromatic Number. The Theory and Applications of Graphs, pp. 557–576. Wiley, New York (1981)
Wagon, S.: A bound on the chromatic number of graphs without certain induced subgraphs. J. Combin. Theory Ser. B 29, 345–346 (1980)
Wang, X., Wu, B.: Upper bounds on the chromatic number of triangle-free graphs with a forbidden subtree. J. Combin. Optim. 33, 28–34 (2017)