不含2K2为导出子图的图的染色

摘要

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.%利用强完美图定理，得到不含{2K2、C4、C5}为导出子图的图是完美图。进而证明了每一个不含{2K2、C4}为导出子图的图是(ω(G)+1)可着色的，并且给出一类满足不含{2K2、C4}为导出子图且χ(G)=ω(G)+1的图类，其中ω(G)和χ(G)分别为图G的团数和色数。