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

Colouring for 2K_2-free Graphs

利用强完美图定理,得到不含{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.