|
|||||
|
|
| 禁用子图为P3∪mP2的图色数上界 | |
| 引用本文： | 王晓.禁用子图为P3∪mP2的图色数上界[J].商洛学院学报,2022(4):60-62. |
| 作者姓名： | 王晓 |
| 作者单位： | 商洛学院数学与计算机应用学院 |
| 基金项目： | 陕西省教育厅专项科研计划项目（16JK1243）； |
| 摘 要： | Gyárfás在完美图概念的基础上，提出了色界函数的概念，并给出猜想：对于给定的森林F，存在整数函数f (F, x)使得每一个以F为禁用子图的图G都满足χ(G)≤f (F,ω(G))，其中χ(G)和ω(G)分别表示图G的色数和团数。通过分析禁用子图为P3∪P2的图结构，给出色界函数f (P3∪P2,ω(G))的一个上界；并且以此为基础，得到禁用子图为P3∪mP2的图色数上界。 |
| 关 键 词： | 色数 团数 色界函数 禁用子图 |