不含3K_1+K_2和C_4为导出子图的图的色数

作者：王晓; 汪小黎

来源：计算机工程与应用, 2015, (19): 50-52.

• 色数
• 限制子图
• &chi
• -界函数
• 完美图 chromatic number
• forbidden subgraph
• &chi
• -bound function
• perfect graph

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

• 单位
  商洛学院