论文研究 不含3K1 K2和C4为导出子图的图的色数.pdf

Gyárfás曾猜想:对于每一个不含森林[F]作为导出子图的图[G],存在整数函数[f(F,ω(G))]使得[χ(G)f(F,ω(G))],其中[χ(G)]和[ω(G)]分别表示图的色数和团数。以强完美图定理为基础,通过对不含[3K1 K2]和[C4]作为导出子图的图的结构进行分析,根据图的独立数进行分类讨论,得到该类图色数的关于团数线性函数的表达式的上界。