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

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

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.