不含K_1+P_3和C_4作为导出子图的图的色数  

On Chromatic Number of {K_1 +P_3,C_4}-free Graphs

作　　者：段芳[1] 

机构地区：[1]新疆师范大学数学科学学院,新疆乌鲁木齐830054

出　　处：《新疆师范大学学报（自然科学版）》2014年第1期78-80,共3页Journal of Xinjiang Normal University(Natural Sciences Edition)

基　　金：新疆师范大学优秀青年教师科研启动基金资助(XJNU1213)

摘　　要：Erodo¨s证明了对于一个图G,χ(G)-ω(G)可以任意大。因此,对一般图而言,其色数不一定能找到一个与团数有关的上界。文章主要研究了一类F-free图的色数和团数的关系。得到了如果图G是一个不含K1+P3和C4作为导出子图的图,那么当α(G)≥3时,χ(G)=ω(G);当α(G)=2时,χ(G)n≤2ω(G)。In general ,there is no upper bound on the chromatic number of a graph in terms of its clique number ,since by a classical result of Erodo＆#168;swe know that the differenceχ（G） - ω（G） can be arbi-trarily large .In this thesis ,we shall focus on F -free graphs and obtain results that the chromatic number of F -free graphs has upper bound in terms of their clique number .If G is a{K1 ＋ P3 ,C4} -free graph , thenχ（G ）= ω（G ） forα（G ） ≥ 3 ,andχ（G ） ≤ 2ω（G ） forα（G ）=2 .

关 键 词：色数 团数 F-free图 

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