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