×

Upper bounds on the chromatic number of triangle-free graphs with a forbidden subtree. (English) Zbl 1364.05031

Summary: A. Gyárfás [Zastosow. Mat. 19, No. 3–4, 413–441 (1987; Zbl 0718.05041)] conjectured that for a given forest \(F\), there exists an integer function \(f(F,x)\) such that \(\chi (G)\leq 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 B. Randerath and I. Schiermeyer [Australas. J. Comb. 26, 3–9 (2002; Zbl 1018.05036)] and a result of A. Gyárfás et al. [Discrete Math. 30, 235–244 (1980; Zbl 0475.05027)]. 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\geq 4\) and \(T\not\cong K_{1,3}\).

MSC:

05C15 Coloring of graphs and hypergraphs
05C05 Trees
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
Full Text: DOI

References:

[1] Brandt S (2002) Triangle-free graphs and forbidden subgraphs. Discret Appl Math 120:25-33 · Zbl 1003.05039 · doi:10.1016/S0166-218X(01)00277-3
[2] Brooks RL (1941) On colouring the nodes of a network. Math Proc Camb Philos Soc 37:194-197 · Zbl 0027.26403 · doi:10.1017/S030500410002168X
[3] Erdős P (1959) Graph theory and probability. Can J Math 11:34-38 · Zbl 0084.39602 · doi:10.4153/CJM-1959-003-9
[4] Gyárfás A (1987) Problems from the world surrounding perfect graphs. Zastos Mat 19:413-441 · Zbl 0718.05041
[5] Gyárfás A, Szemerédi E, Tuza Z (1980) Induced subtrees in graphs of large chromatic number. Discret Math 30:235-244 · Zbl 0475.05027 · doi:10.1016/0012-365X(80)90230-7
[6] Jensen TR, Toft B (1995) Graph coloring problems. Wiley, New York · Zbl 0855.05054
[7] Randerath B (2004) 3-colorability and forbidden subgraphs. I: characterizing pairs. Discret Math 276:313-325 · Zbl 1031.05052 · doi:10.1016/S0012-365X(03)00312-1
[8] Randerath B, Schiermeyer I (2002) A note on Brooks’ theorem for triangle-free graphs. Aust J Comb 26:3-9 · Zbl 1018.05036
[9] Randerath B, Schiermeyer I (2004) Vertex colouring and forbidden subgraphs—a survey. Graph Comb 20:1-40 · Zbl 1056.05065 · doi:10.1007/s00373-003-0540-1
[10] Reed \[B (1998) \omega, \Delta\] ω,Δ and \[\chi\] χ. J Graph Theory 37:177-212 · Zbl 0980.05026 · doi:10.1002/(SICI)1097-0118(199804)27:4<177::AID-JGT1>3.0.CO;2-K
[11] Wagon S (1980) A bound on the chromatic number of graphs without certain induced subgraphs. J Comb Theory Ser B 29:345-346 · Zbl 0457.05032 · doi:10.1016/0095-8956(80)90093-3
[12] West DB (2001) Introduction to graph theory, 2nd edn. Prentice Hall, Upper Saddle River
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.