王晓

（商洛学院数学与计算机应用学院，陕西商洛 726000）

色数和团数是图的两个重要参数，著名图论专家Erdös利用概率的方法证明了色数和团数的差值可以是任意大的整数[1-2]。显然，一个图的色数至少等于其团数，这就促使研究者去考虑色数和团数相等的图。一个k-可着色的图和阶数为k的完全图的不交并所构成图满足色数和团数相等。因此，单纯考虑图本身的色数和团数相等意义不大。Berge[3]提出了完美图的概念：不但要求图本身的色数和团数相等，同时要满足其所有的导出子图的色数和团数也相等。与此同时，Berge提出了两个关于完美图的猜想（弱完美图猜想和强完美图猜想）。弱完美图猜想是：一个图是完美图当且仅当其补图是完美图，随后被Lovász[4]证明，称为完美图定理。强完美图猜想是：一个图是完美图当且仅当其本身和其补图都不含长度大于等于5的奇长圈为导出子图，在2006年被Chudnovsky等[5]证明，称为强完美图定理。基于完美图的定义，Gyárfás[6]提出了图的色界函数的概念，即：什么样的图存在以团数为变量的函数使得其任意导出子图的色数都以这个函数为上界。 在文献[6]中，Gyárfás给出了猜想 1。

猜想1[6]设F是一个森林，存在整数函数f(F,x)使得对于每一个以F为禁用子图的图G都满足 χ(G)≤ f(F,ω(G))，其中 χ(G)和 ω(G)分别表示图G的色数和团数。

围绕猜想1，众多学者进行了广泛的研究，已有丰富的结果[7-13]。特别地，Wagon[9]证明了禁用子图为两条独立边的图的一个色界函数为Choudum[12]研究了独立数小于等于2的图色界函数。……