不含某些图作为导出子图的图的色数

On Chromatic Number of Graphs without Certain Induced Subgraphs

Erods证明了对于任意一个图G,χ(G)-ω(G)可以任意大。因此,对一般图而言,其色数不一定能找到一个与团数有关的上界。文章主要讨论一类特殊的F-free图的色数和团数的关系。设图G=(V,E)是一个不含K1,k+1+e、C4和C4+e为导出子图的连通图,不是星图和奇圈。若α(G)≥k≥3,则χ(G)≤(k(k-1)/2)ω(G)。

In general, there is no upper bound on the chromatic number of a graph in terms of its clique num？ber, since by a classical result of Erodoswe know that the differenceχ（ G） -ω（ G） can be arbitrarily 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. LetG be a{K1,k＋1 ＋ e,C4,C4 ＋ e} -free graph,ifα（G） ≥k≥3,thenχ（ G） ≤（ k（ k - 1）/2）ω（ G） .