Let G and H be two induced subgraph isomorphic to conjectured that, for every tree function, depending only on T graphs. We say that G induces H if G has an H. A. Gyarfas and D. Sumner, independently, T, there exists ...Let G and H be two induced subgraph isomorphic to conjectured that, for every tree function, depending only on T graphs. We say that G induces H if G has an H. A. Gyarfas and D. Sumner, independently, T, there exists a function fT, called binding with the property that every graph G with chromatic number fT（ω（G）） induces T. A. Gyarfas, E. Szemeedi and Z. Tuza confirmed 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. Gyarfas et al. onto general graphs. A. Scott proved an interesting topological version of this conjecture asserting that for every integer k and every tree T of radius r, every graph G with co（G） ≤ k and sufficient large chromatic number induces a subdivision of T of which each edge is subdivided at most O（14^r-1（r - 1）!） times. We extend the approach of A. Gyarfas 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（6^r-2） times.展开更多
基金Acknowledgements The authors thank the referees for their valuable comments. This work was partially supported by the National Natural Science Foundation of China （Grant Nos. 11331003, 11571180） and a Project Funded by the Priority Academic Program Development of Jiangsu Higher Education Institutions.
文摘Let G and H be two induced subgraph isomorphic to conjectured that, for every tree function, depending only on T graphs. We say that G induces H if G has an H. A. Gyarfas and D. Sumner, independently, T, there exists a function fT, called binding with the property that every graph G with chromatic number fT（ω（G）） induces T. A. Gyarfas, E. Szemeedi and Z. Tuza confirmed 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. Gyarfas et al. onto general graphs. A. Scott proved an interesting topological version of this conjecture asserting that for every integer k and every tree T of radius r, every graph G with co（G） ≤ k and sufficient large chromatic number induces a subdivision of T of which each edge is subdivided at most O（14^r-1（r - 1）!） times. We extend the approach of A. Gyarfas 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（6^r-2） times.
