Chromatic number and subtrees of graphs

Abstract

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 f_T; called binding function, depending only on T with the property that every graph G with chromatic number f_T(ω(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(14^r–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(6^r–2) times.

Key words： Chromatic number; clique number; induced tree; subdivision

References

1 Beineke L. Derived graphs and digraphs. In: Sachs H, ed. Beitrage zur Graphentheorie. Leipzig: Teubner, 1968, 17–33

2 Bondy J, Murty U. Graph Theory. Berlin: Springer, 2008

3 Chudnovsky M, Penev I, Scott A, Trotignon N. Substitution and _-boundedness. J Combin Theory Ser B, 2013, 103: 567–586

4 Chudnovsky M, Robertson N, Seymour P, Thomas R. The strong perfect graph theorem. Ann of Math, 2006, 164: 51–229

5 Descartes B. A three colour problem. Eureka, 1947, 21

6 Erdos P. Graph theory and probability. Canad J Math, 1959, 11: 34–38

7 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

9 Gy_arf_as A, Szemer_edi E, Tuza Z. Induced subtrees in graphs of large chromatic number. Discrete Math, 1980, 30: 235–244

10 Kierstead H, Penrice S. Radius two trees specify _(G)-bounded classes. J Graph Theory, 1994, 18: 119–129

11 Kierstead H, Zhu Y. Radius three trees in graphs with large chromatic number. SIAM J Discrete Math, 2004, 17: 571–581

12 Mycielski J. Sur le coloriage des graphes. Colloq Math, 1955, 3: 161–162

13 Scott A. Induced trees in graphs of large chromatic number. J Graph Theory, 1997, 24: 297–311

14 Sumner D. Subtrees of a graph and chromatic number. In: The Theory and Applications of Graphs. New York: John Wiley & Sons, 1981: 557–576

15 Vizing V. The chromatic class of a multigraph. Kibernetika (Kiev), 1965, 3: 29-39

16 Zykov A. On some properties of linear complexes. Mat Sb, 1949, 24: 313–319 (in Russian)