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

On chromatic number of {3K_1+ K_2,C_4}-free graphs

作　　者：王晓[1] 汪小黎[1] 

机构地区：[1]商洛学院数学与计算机应用学院,陕西商洛726000

出　　处：《计算机工程与应用》2015年第19期50-52,共3页Computer Engineering and Applications

基　　金：陕西省教育厅基金(No.12JK089);陕西省科技厅基金(No.2014JM2-1007);商洛学院科研基金(No.12SKY011)

摘　　要：Gyárfás曾猜想:对于每一个不含森林F作为导出子图的图G,存在整数函数f(F,ω(G))使得χ(G)≤f(F,ω(G)),其中χ(G)和ω(G)分别表示图的色数和团数。以强完美图定理为基础,通过对不含3K1+K2和C4作为导出子图的图的结构进行分析,根据图的独立数进行分类讨论,得到该类图色数的关于团数线性函数的表达式的上界。Gyfarfas conjured that for a given forest F, there exists an integer function f（F, w（G）） such that x（G） ≤f（F, co（G）） for any F -free graph G, where x（G） and co（G） are the chromatic number and clique number of G, respectively. By the strong perfect graph theorem, the structural characterization of {3K1 ＋ K2, C4} -free graphs is analyzed, according to classi- fication for independent number of graphs, the upper bound, with linear function in term of clique number, on chromatic number of {3K1 ＋k2, C4} -free graphs is obtained.

关 键 词：色数 限制子图 χ-界函数 完美图 

分 类 号：O157.5[理学—数学]