计算机工程与应用 ›› 2015, Vol. 51 ›› Issue (19): 50-52.

• 理论研究、研发设计 • 上一篇    下一篇

不含3K1+K2和C4为导出子图的图的色数

王  晓,汪小黎   

  1. 商洛学院 数学与计算机应用学院,陕西 商洛 726000
  • 出版日期:2015-09-30 发布日期:2015-10-13

On chromatic number of {3K1+K2,C4}-free graphs

WANG Xiao, WANG Xiaoli   

  1. College of Mathematics and Computer Application, Shangluo University, Shangluo, Shannxi 726000
  • Online:2015-09-30 Published:2015-10-13

摘要: Gyárfás曾猜想:对于每一个不含森林[F]作为导出子图的图[G],存在整数函数[f(F,ω(G))]使得[χ(G)f(F,ω(G))],其中[χ(G)]和[ω(G)]分别表示图的色数和团数。以强完美图定理为基础,通过对不含[3K1+K2]和[C4]作为导出子图的图的结构进行分析,根据图的独立数进行分类讨论,得到该类图色数的关于团数线性函数的表达式的上界。

关键词: 色数, 限制子图, [&chi, ]-界函数, 完美图

Abstract: Gyárfás conjured that for a given forest[F], there exists an integer function[f(F,ω(G))] such that [χ(G)f(F,ω(G))] for any[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[{3K1+K2,?C4}]-free graphs is analyzed, according to classification 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.

Key words: chromatic number, forbidden subgraph, [χ]-bound function, perfect graph