关于诱导子树与图的色数的一个注记  

A note on induced subtrees and chromatic number of graphs

作　　者：张莹丽[1] 许宝刚[1] ZHANG YingLi XU BaoGang

机构地区：[1]南京师范大学数学科学学院,南京210023

出　　处：《中国科学：数学》2017年第5期667-672,共6页Scientia Sinica：Mathematica

基　　金：国家自然科学基金(批准号:11331003和11571180)资助项目

摘　　要：Gyrfs(1975)和Sumner(1981)分别独立地提出了以下猜想:对于任意的树T,存在一个函数f_T(x)使得每一个色数大于f_T(ω(G))的图均包含T作为诱导子图,其中ω(G)表示图G的团数.Gyrfs等(1980)证明了,若一个图G不含三角形和长为4的圈,则G含有任一个χ(G)个顶点的树作为诱导子图.另外,他们还证明了,若G不含三角形,且χ(G)≥m+n,则G一定包含一个特殊的树(m,n)-mop作为诱导子图.本文推广了Gyrfs等(1980)的这两个结果,证明了(1)若图G的任一个顶点至多含在k个三角形和l个长为4的圈中,且χ(G)≥t+2k+2k,则G包含任一个t个点的树作为诱导子图;(2)若图G中的每一个顶点至多包含在k个三角形中,且不能够诱导出T,则χ(G)<m(k+1)+n,其中T为(m,n)-mop.Gyarfas（1975） and Sumner（1981） independently,conjectured that for every tree T,there exists an integer-valued function f_T（x） such that every graph G of chromatic number larger than fT（ω（G）） contains T as an induced subgraph,where ω（G） is the clique number of G.Gyarfas et al.proved that if G contains no triangles and cycles of length 4,then G contains every tree on x（G） vertices as an induced subgraph.Besides this,they also confirmed that if G contains no triangles and x（G） ≥ m ＋ n,then G can induce an（m,n）-mop which is a special tree.In this note,we generalize these two results of Gyrfs et al.and prove that（1） if every vertex of G is contained in at most k triangles and l cycles of length 4,and x（G） ≥ t ＋ 2k ＋ 2l,then G contains every tree on t vertices as an induced subgraph;（2） if every vertex of G is contained in at most k triangles,and x（G） ≥ m（k ＋ 1） ＋ n,then G contains an（m,n）-mop as an induced subgraph.

关 键 词：色数 诱导子树 三角形 

分 类 号：O157.5[理学—数学]