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

Upper Bound of Chromatic Number for {3K_1,K_1+C_4}-free Graphs

在完美图的基础上,Gyárfás提出了用f (ω)表示图的色数上界的概念。通过对不含3K_1和K_1+C_4为导出子图的图结构进行分析,得到了该类图色数的关于团数线性函数表达式的上界。此结果改进了Choudum等关于此类图的结论。

Gyárfás improves the conception of perfect graphs,and gives the upper bound with f (ω) on chromatic number of graphs. By analyzing of the structural characterization of{3K1,K1 + C4}-free graphs,the upper bound,with linear function in term of clique number,on chromatic number of { 3K1,K1 + C4}-free graphs is obtained. This result improves Choudum etl.'s result for these graphs.