Please wait a minute...
Frontiers of Mathematics in China

ISSN 1673-3452

ISSN 1673-3576(Online)

CN 11-5739/O1

邮发代号 80-964

2019 Impact Factor: 1.03

Frontiers of Mathematics in China  2017, Vol. 12 Issue (2): 441-457   https://doi.org/10.1007/s11464-016-0613-0
  本期目录
Chromatic number and subtrees of graphs
Baogang XU,Yingli ZHANG()
Institute of Mathematics, School of Mathematical Sciences, Nanjing Normal University, Nanjing 210023, China
 全文: PDF(116 KB)  
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 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.

Key wordsChromatic number    clique number    induced tree    subdivision
收稿日期: 2015-10-07      出版日期: 2016-12-27
Corresponding Author(s): Yingli ZHANG   
 引用本文:   
. [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.
 链接本文:  
https://academic.hep.com.cn/fmc/CN/10.1007/s11464-016-0613-0
https://academic.hep.com.cn/fmc/CN/Y2017/V12/I2/441
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
https://doi.org/10.1007/978-1-84628-970-5
3 Chudnovsky M, Penev I, Scott A, Trotignon N. Substitution and _-boundedness. J Combin Theory Ser B, 2013, 103: 567–586
https://doi.org/10.1016/j.jctb.2013.02.004
4 Chudnovsky M, Robertson N, Seymour P, Thomas R. The strong perfect graph theorem. Ann of Math, 2006, 164: 51–229
https://doi.org/10.4007/annals.2006.164.51
5 Descartes B. A three colour problem. Eureka, 1947, 21
6 Erdos P. Graph theory and probability. Canad J Math, 1959, 11: 34–38
https://doi.org/10.4153/CJM-1959-003-9
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
https://doi.org/10.1016/0012-365X(80)90230-7
10 Kierstead H, Penrice S. Radius two trees specify _(G)-bounded classes. J Graph Theory, 1994, 18: 119–129
https://doi.org/10.1002/jgt.3190180203
11 Kierstead H, Zhu Y. Radius three trees in graphs with large chromatic number. SIAM J Discrete Math, 2004, 17: 571–581
https://doi.org/10.1137/S0895480198339869
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
https://doi.org/10.1002/(SICI)1097-0118(199704)24:4<297::AID-JGT2>3.0.CO;2-J
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
https://doi.org/10.1007/bf01885700
16 Zykov A. On some properties of linear complexes. Mat Sb, 1949, 24: 313–319 (in Russian)
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed