Let Gand Hbe two graphs. We say that G induces H if G has an induced subgraph isomorphic to H. A. Gyárfás and D. Sumner, independently, conjectured that, for every tree T; there exists a function fT; called binding function, depending only on T with the property that every graph G with chromatic number fT(ω(G)) induces T. A. Gyárfás, E. Szemerédi and Z. Tuza conrmed the conjecture for all trees of radius two on triangle-free graphs, and H. Kierstead and S. Penrice generalized the approach and the conclusion of A. Gyárfás et al. onto general graphs. A. Scott proved an interesting topological version of this conjecture asserting that for every integer kand every tree T of radius r, every graph G with ω(G)≤k and sufficient large chromatic number induces a subdivision of T of which each edge is subdivided at most O(14r–1(r–1)!) times. We extend the approach of A. Gyárfás and present a binding function for trees obtained by identifying one end of a path and the center of a star. We also improve A. Scott's upper bound by modifying his subtree structure and partition technique, and show that for every integer k and every tree T of radius r; every graph with ω(G)≤k and sufficient large chromatic number induces a subdivision of T of which each edge is subdivided at most O(6r–2) times.
. [J]. Frontiers of Mathematics in China, 2017, 12(2): 441-457.
Baogang XU,Yingli ZHANG. Chromatic number and subtrees of graphs. Front. Math. China, 2017, 12(2): 441-457.
Gy_arf_as A. On Ramsey covering-numbers. In: In_nite and Finite Sets. Colloquia Mathematic Societatis J_anos Bolyai 10. New York: North-Holland/American Elsevier, 1975, 801–816
8
Gy_arf_as A. Problems from the world surrounding perfect graphs. Zastosow Mat, 1987, 19: 413–441