让的 G 和 H 是二张图。如果 G 有对 H 同形的导致的 subgraph,我们说 G 导致 H:A。Gy
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.