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

王晓

（商洛学院数学与计算机应用学院，陕西商洛726000）

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

王晓

（商洛学院数学与计算机应用学院，陕西商洛726000）

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

色数；团数；导出子图

设χ(G)，ω(G)分别表示图G的顶点色数和团数，显然对于任一图G，有χ(G)≥ω(G)[1]，且由文献[2-3]中Erdos的经典结论，可知图的色数和团数之差χ(G)-ω(G)可以任意大。若对于G的任意导出子图H都有χ(H)≥ω(H)，则称图G为完美图，Berge提出的著名的完美图猜想最近已由Seymour等四位数学家证明[4-5]。Gyárfás在完美图的基础上，提出了与团数有关的图的色数上界的概念[6]，对于任意的图G∈Φ，如果存在整数函数f使得χ(G)≤f(ω(G))，则称Φ是关于f为色数界的图类。显然以f(x)=x为色数界的图类就是完美图。对任意给定图H，如果图G不含与H同构的图为导出子图，则称图G是H-free(不含H为导出子图)的。Gyárfás给出猜想[6]：设F是一个森林，对于每一个F-free的图G，存在整数函数f(F,ω(G))使得χ(G)≤f(F,ω(G))。

Wagon[7]证明了，Hoang[8]证明了。关于限制子图的色数的更多结论可参阅文献[9-11]。本文证明了不含2K2、C4和C5为导出子图的图是完美图，进而证明了每一个不含2K2和C4为导出子图的图是(ω(G)+1)可着色的，并且给出一类满足不含2K2和C4为导出子图且χ(G)=ω(G)+1的图类，这里2K2表示两条独立边。

1 预备知识

设G=(V(G),E(G))表示一个图，其中V(G)和E(G)分别表示图G的顶点集和边集。给定ν∈V(G)和A⊆V(G)，NG(ν)和G[A]分别表示图G中ν的邻点集和由A导出的子图。文中涉及到的其他术语、符号参考文献[1]。

设H为图G的导出子图，若H为长度至少为5的奇圈，则称H为G奇洞；若H为长度至少为5的奇圈的补图，则称H为G的补奇洞。不含奇洞和补奇洞的图称为Berge图。由Berge提出，Seymour等证明的强完美图定理为：

定理1[4]图G是完美图当且仅当图G是Berge图。

图G不含补奇洞即其补图不含奇洞，所以图G为Berge图当且仅当G和都不含奇洞。所以强完美图定理也可表示为：

定理2[4]图G为完美图示当且仅当G和都不含奇洞。

对于一些常见的完美图有：

命题1[4]Split图、二部图及其补图都是完美图。

2 定理及其证明

定理3若图G不含2K2，C4和C5为导出子图，则图G是完美图，即χ(G)=ω(G)。

证明显然，图G不含长度大于等于6的圈为导出子图，否则与G不含2K2为导出子图矛盾。又由图G不含C5为导出子图，所以图G不含奇洞。证明G的补图也不含奇洞。假设含有C5为导出子图，由于，所以G含有C5为导出子图，矛盾。又若中含有长度大于5的奇洞，设为Cm(m≥7)，则取Cm中顶点都不相邻的两条边ν1ν2，u1u2∈E(Cm),有，因而，即图G中含有C4作为导出子图，矛盾。由强完美图定理2，图G是完美图。

定理3若图G不含2K2和C4为导出子图，则χ(G)≤ω(G)+1，且存在等号成立的图。

证明若图是不连通的，只需要考虑每个连通分支，故不失一般性，假设G是连通图。设S为图G的一个最大独立集，则V(G)S中的每个点在S中至少有一个邻点。令，，则A,B,S构成V(G)的一个划分，且有如下结论。

结论1G(A)是完全图。

假设存在x,y∈A，但xy∉E(G)。由于x,y在 S中都仅有一个邻点，分别设为。若，则是独立集，与S是最大独立集矛盾；若，则，矛盾。

结论2G[B]是完全图。

假设存在x，y∈B，但xy∉E(G)。若x,y在S中没有公共的邻点，即NG(x)∩NG(y)∩S=φ，设分别是x,y在S中各自的邻点，则，矛盾；若x,y在S中仅有一个公共的邻点，即NG(x)∩NG(y)∩S={u}，则x,y在S中还至少存在异于u的各自另外一个邻点，设为,即，矛盾；若x,y在S中至少有2个公共的邻点，即，设u,ν∈NG(x)∩NG(y)∩S，则G[x,y,u,ν]≅C4，矛盾。

由结论1和结论2，可知G[A∪B]是二部图的补图，即为完美图。而S是独立集，所以χ(G)≤ω(G)+1。

构造满足不含2K2和C4为导出子图且χ(G)= ω(G)+1的图G0。设x,y是完全图Kn中的两个点，ν1,ν2是路P3=ν1ν2ν3的两个端点，，，，图G0是由Kn和P3构成的阶为n+3的图，满足V(G0)=V(Kn)∪V(P3)，E(G0)=E(Kn)∪E(P3)∪Eν1Eν2Eν3。显然图G0满足不含2K2和C4为导出子图，且ω(G0)=n。考虑G0的色数χ(G0)，由G0的子图Kn的着色扩充到G0的着色c，Kn至少需要n种颜色（每个顶点一种颜色），不妨设c(x)=1，c(y)=n,由于ν1与Kn中除了y外的所有顶点都相邻，所以只能c(ν1)=n，否则χ(G0)=ω(G0)+1；同理由ν2与Kn中除了x,y外的所有顶点都相邻，所以只能c(ν2)=1；由ν3与Kn中除了y外的所有顶点都相邻，且ν2ν3∈E(G0)，所以ν3只能着1,2,…,n外的另外一种颜色，故χ(G0)=ω(G0)+1。

[1]Reinhard D.Graph theory(Second Edition)[M].Hong Kong：Springer-Verlag,2000：95-122.

[2]Erdos P.Graph theory and probability[J].Canad J Math, 1959,11：34-38.

[3]ReedB.ω,Δandχ[J].Journalofgraphtheory,1998,374：177-212.

[4]ChudnovskyM,RobertsonN,SeymourP.Thestrongperfect graphtheorem[J].AnnalsofMathematics,2006,164：51-229.

[5]宋春伟.强完美图定理及相关问题[J].数学进展,2008,37 (2)：153-163.

[6]Gyárfás A.Problems from the world surrounding perfect graphs[J].Zastow Mat,1987,19：413-441.

[7]Wagon S.A bound on the chromatic number of graphs without certain induced subgraphs[J].Journal of Combin Theory,Series B,1980,29：345-346.

[8]Hoang C T,McDiarmid C.On the divisibility of graphs[J].Discrete Math,2002,242：145-156.

[9]张东翰.图Dn,4的邻点强可区别的全染色[J].商洛学院学报，2014,28(6)：8-9.

[10]Duan F,Wu B Y.On chromatic number of graphs without certaininducedsubgraphs[J].Arscombinatoria.2011(7)：33-4.

[11]段芳,张维娟.不含2K1+K2和C4作为导出子图的图的色数[J].华东师范大学学报：自然科学版,2014(1)：9-12.

（责任编辑：李堆淑）

Colouring for 2K2-free Graphs

WANG Xiao
（College of Mathematics and Computer Application,Shangluo University,Shangluo726000,Shaanxi）

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.

chromatic number;clique number;induced subgraph

O172

A

1674-0033（2015）02-0003-02

10.13440/j.slxy.1674-0033.2015.02.001

2014-12-18

商洛学院科研基金项目（09SKY005）

王晓，男，河南南阳人，硕士，讲师