禁用子图为P_(3)∪mP_(2)的图色数上界  

Upper Bound on the Chromatic Number for P_(3)∪mP_(2)-free Graphs

作　　者：王晓 WANG Xiao(College of Mathematics and Computer Application,Shangluo University,Shangluo 726000,Shaanxi)

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

出　　处：《商洛学院学报》2022年第4期60-62,共3页Journal of Shangluo University

基　　金：陕西省教育厅专项科研计划项目(16JK1243)。

摘　　要：Gyárfás在完美图概念的基础上,提出了色界函数的概念,并给出猜想:对于给定的森林F,存在整数函数f (F, x)使得每一个以F为禁用子图的图G都满足χ(G)≤f (F,ω(G)),其中χ(G)和ω(G)分别表示图G的色数和团数。通过分析禁用子图为P_(3)∪P_(2)的图结构,给出色界函数f (P_(3)∪P_(2),ω(G))的一个上界;并且以此为基础,得到禁用子图为P_(3)∪mP_(2)的图色数上界。Gyárfás introduced the concept of the binding function of chromatic number thereby extending the notation of perfect graphs,and he conjectured that for each forest F,there exists an integer function f(F,x)such thatχ(G)≤f(F,ω(G))for every F-free graph G,whereχ(G)andω(G)are the chromatic number and clique number of G respectively.By analyzing of the structure characterization of P_(3)∪P_(2)-free graphs,the upper bound on chromatic number of P_(3)∪P_(2)-free graphs was obtained.Using it as a base,the binding function of chromatic number for P_(3)∪mP_(2)-free graphs was given.

关 键 词：色数 团数 色界函数 禁用子图 

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