不含P_3∪P_2和C_4为导出子图的图的色数  

The Chromatic Number of {P_3∪P_2,C_4}-free Graphs

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

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

出　　处：《河南科学》2015年第10期1701-1705,共5页Henan Science

基　　金：陕西省科技厅自然科学基金资助项目(2014JM2-1007);商洛学院科研基金(12SKY011)

摘　　要：Gyárfás曾猜想:对于每一个不含森林F作为导出子图的图G,存在整数函数f(F,x)使得χ(G)≤f(F,ω(G)),其中χ(G)和ω(G)分别表示图G的色数和团数.以强完美图定理为基础,通过对不含P3?P2和C4作为导出子图的图的结构进行分析,得到χ(G)≤min{ω(G)+2,5ω(G)/4},其中G为不含P3∪P2和C4作为导出子图的图.Gyrrfas conjured that for a given forest F, there exists an integer function f（F,x） such that χ（C）≤f（F, to（C）） for each F-free graph G, where χ（G） and ω（G） are the chromatic number and clique number of G, respectively. By the strong perfect graph theorem, the structural characterization of {P3∪P2, C4} -free graphs is analyzed, the result that x（G） ≤ min {to（G）＋ 2, [5ω（G）/4]} is obtained, where G is {P3∪P2, C4}-free.

关 键 词：色数 导出子图 团数 

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