摘要
利用强完美图定理,得到不含{2K2、C4、C5}为导出子图的图是完美图。进而证明了每一个不含{2K2、C4}为导出子图的图是(ω(G)+1)可着色的,并且给出一类满足不含{2K2、C4}为导出子图且χ(G)=ω(G)+1的图类,其中ω(G)和χ(G)分别为图G的团数和色数。
By the strong perfect graph theorem, the result that every{2K2, C4, C5}-free graph is perfect graph was obtained. Moreover, the result that every {2K2, C4}-free graph is (ω(G)+1)-colourable was proved, a kind of graphs satisfying {2K2, C4}-free and χ(G)=ω(G)+1 was given, where χ(G) and ω(G) denote chromatic number and clique number respectively.
出处
《商洛学院学报》
2015年第2期3-4,共2页
Journal of Shangluo University
基金
商洛学院科研基金项目(09SKY005)
关键词
色数
团数
导出子图
chromatic number
clique number
induced subgraph