摘要
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 .
出处
《新疆师范大学学报（自然科学版）》
2014年第1期78-80,共3页
Journal of Xinjiang Normal University(Natural Sciences Edition)
基金
新疆师范大学优秀青年教师科研启动基金资助(XJNU1213)
关键词
色数
团数
F-free图
Clique number
Chromatic number
F-free graph
