位置:成果数据库 > 期刊 > 期刊详情页
Chromatic number and subtrees of graphs
  • ISSN号:0253-374X
  • 期刊名称:《同济大学学报:自然科学版》
  • 时间:0
  • 分类:O157.5[理学—数学;理学—基础数学] O189.1[理学—数学;理学—基础数学]
  • 作者机构:Institute of Mathematics, School of Mathematical Sciences, Nanjing Normal University,Nanjing 210023, China
  • 相关基金: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.
中文摘要:

让的 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.

同期刊论文项目
同项目期刊论文
期刊信息
  • 《同济大学学报:自然科学版》
  • 北大核心期刊(2011版)
  • 主管单位:教育部
  • 主办单位:同济大学
  • 主编:李杰
  • 地址:上海四平路1239号
  • 邮编:200092
  • 邮箱:zrxb@tongji.edu.cn
  • 电话:021-65982344
  • 国际标准刊号:ISSN:0253-374X
  • 国内统一刊号:ISSN:31-1267/N
  • 邮发代号:4-260
  • 获奖情况:
  • 国家双百期刊,第二届国家期刊奖重点科技期刊奖,1999年全国优秀高校自然科学学报一等奖
  • 国内外数据库收录:
  • 俄罗斯文摘杂志,美国化学文摘(网络版),美国数学评论(网络版),德国数学文摘,荷兰文摘与引文数据库,美国工程索引,美国剑桥科学文摘,中国中国科技核心期刊,中国北大核心期刊(2004版),中国北大核心期刊(2008版),中国北大核心期刊(2011版),中国北大核心期刊(2014版),中国北大核心期刊(2000版)
  • 被引量:34557