禁用子图为2K2和K1+C4的图的色数

汪小黎，王晓

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

对于图G的任一导出子图H，如果其色数χ(H)与团数ω(H)相等，则将图G称为完美图。在完美图的基础上，Gyárfás[1]提出了用函数 f(ω)表示图的色数上界的概念，完美图就是以f(ω)=x为色数界的图类。对于给定的图H，如果图G不含与H同构的导出子图，则称H是图G的禁用子图或者图 G是 H-free 的。在文献[1]中，Gyárfás给出猜想：令F为一森林，则对于每一个F-free的图G，都存在整数函数 f(x,y)使得 χ(G)≤f(F,ω(G))。关于此猜想的一些结论可参阅文献[2-6]。特别地，在文献[7]中，Wagon 证明了 f(2K2,ω)≤(ω2+ω)/2；在文献[8]中，证明了{2K2,C4,C5}-free的图是完美图，并且得到了 f({2K2,C4},ω)≤ω+1，其中 2K2表示两条独立的边。

设G1和G2为两个图，它们的联图，记为G1+G2，表示满足V(G1+G2)=V(G1)∪V(G2)和E(G1+G2)=E(G1)∪E(G2)∪{xy|x∈V(G1),y∈V(G2)}的图。设 3K1表示三个独立点，在文献[9]中Choudum等给出f({3K1,K1+C4},ω)≤2ω。

本文考虑 {2K2,K1+C4}-free的图的色数界函数，利用强完美图定理，得到了f({2K2,K1+C4},ω)≤ω+5。

1 预备知识

本文所研究的图均为有限、简单、无向图。对于图G，其顶点集和边集分别用V(G)和E(G)来表示。设V0⊂V(G)，则NG(V0)和G[V0]分别表示图G中与V0中的某一个点相邻且不在V0中的点的集合和由顶点子集V0导出的子图。特别地，若V0={v}，则 NG(V0)可简写为 NG(v)。边集 E(G)为空集的图称为空图，若G[V0]为空图，则V0称为图G的独立集。其他文中涉及到的术语和符号可参考文献[10]。

奇洞和补奇洞是完美图定理中的两个重要概念。图G中长度至少为5的导出奇圈称为G的奇洞，图G的补图中的奇洞的补图称为原图的G补奇洞。著名的完美图定理[11-12]由Berge提出，Seymour等证明。

定理1图G是完美图当且仅当图G是Berge图，其中Berge图是不含奇洞和补奇洞的图。

与之等价的另外一种表述形式为：

定理2图G是完美图当且仅当图G和其补图都不含奇洞。

命题1设图G存在一个顶点集的划分V1,V2，使得G[V1]是完全图，G[V2]是独立集和一条边的不交并，则图G为完美图。

证明设H是图G的导出子图，则有V(H)⊆V1或者V(H)⊆V2或者V(H)存在划分V'1,V'2使得但是对任一奇洞，都不存在这三种情形，因此G不含奇洞。图G的补图存在顶点集的划分U1,U2使得[U1]是完全图删掉一条边所得的图，是空图。同理可得，不含奇洞。根据定理2，即有图G为完美图。

如果图G存在一个顶点集的划分V1,V2，使得G[V1]是完全图，G[V2]是独立集，则称图G是Split图。一些常见的完美图有：

命题2[11-12]Split图、二部图及其补图都是完美图。

在文献[8]中，考虑了禁用子图为2K2和C4的图，得到：

定理3[8]设2K2和C4是图G的禁用子图，则有 χ(G)≤ω(G)+1。

2 定理及其证明

定理4设2K2和K1+C4是图G的禁用子图，则有 χ(G)≤ω(G)+5。

证明如果C4也是图G的禁用子图，则根据定理3，可知χ(G)≤ω(G)+1。因此，假设图G含有C4做为其导出子图。为后面的证明方便起见，令A=V(C4)={vi：i∈Z4}，vivi+1∈E(G)，Xi={v∈NG(A)：NG(v)∩A={vi}}，Yij={v∈NG(A)：NG(v)∩A={vi,vj}}，Ri={v∈NG(A)：NG(v)∩A=A{vi}}，M=V(G)[NG(A)∪A]，其中 i,j∈Z4。有如下结论。

结论 1X1∪X2∪M和 X3∪X4或者是空集或者是独立集。

假设 X1∪X2、M 和 X3∪X4都不是空集，因为2K2是图G的禁用子图，所以它们都是独立集。如果存在 u∈X1∪X2，v∈M 使得 uu'∈E(G)，则有G[{u,u',v3,v4}]≌2K2，矛盾。因此 X1∪X2∪M 是独立集。

结论2或者是空图或者是完全二部图。

因为2K2是图G的禁用子图，所以，如果Yi(i+1)≠Ø 中，(i∈Z4)，则 Yi(i+1)是独立集。对于 yi∈Yi(i+1)(i∈Z4)，必然有 yiyi+1∈E(G)，否则有 G[{yi,vi,yi+1,vi+2}]≌2K2，矛盾；同理有 yiyi+2∈E(G)。如果 Yi(i+1)、Y(i+1)(i+2)和 Y(i+2)(i+3)，(i∈Z4)都不为空集，则有 G[{yi,yi+1,yi+2,vi+1,vi+2}]≌K1+C4，矛盾。因此|{Yi(i+1)：Yi(i+1)≠Ø，i∈Z4}|≤2，即或者是空图或者是完全二部图。

结论 3若 Yi(i+2)≠Ø，(i∈Z4)，则 G[Yi(i+2)]或者是完全图，或者是空图，或者是独立集和一条边的不交并。

不失一般性，假设Y13≠Ø且G[Y13]不是完全图不是空图也不是独立集和一条边的不交并，则G[Y13]必然含有P3为其导出子图，即有G[V(P3)∪{v1,v3}]≌K1+C4，矛盾。

结论 4若 Ri≠Ø,(i∈Z4)，则 G[Ri]是完全图且 Ri+2=Ø。

假设ri,r'i∈Ri且 ri,r'i∉E(G)，则 G[ri,r'i,vi-1,vi,vi+1}]≌K1+C4，矛盾。所以G[Ri]是完全图。若存在ri+2∈Ri+2，当 riri+2∈E(G)时，有 G[{ri,ri+2,vi-1,vi,vi+1}]≌K1+C4，矛盾；当 riri+2∉E(G)时，有 G[{ri,ri+2,vi,vi+2}]≌2K2，矛盾。因此有Ri+2=Ø。

结论 5若 Ri≠Ø(i∈Z4)，则 G[Y(i-1)(i+1)]为空图。

设 ri∈Ri，u∈Y(i-1)(i+1)，则有 riu∉E(G)，否则有 G[{ri,u,vi-1,vi,vi+1}]≌K1+C4，矛盾。现假设 u,u'∈Y(i-1)(i+1)且 uu'∈E(G)，则有 G[{u,u',ri,vi}]≌2K2，矛盾。因此G[Y(i-1)(i+1)]为空图。

根据结论 4，令 t=|{|Ri：Ri≠Ø,i∈Z4}|，则 t≤2。下面分三种情况来证明。

情况1t=0。

如果G[Y13]和G[Y24]都不是独立集和一条边的不交并，则由结论3，可知G[Y13∪Y24]或者是二部图，或者是Split图，或者是二部图的补图。根据命题2，可知G[Y13∪Y24]是完美图。如果在G[Y13]和G[Y24]中，有一个是独立集和一条边的不交并，另一个是完全图。根据命题1，可知G[Y13∪Y24]是完美图。即 χ(G[Y13∪Y24])=ω(G[Y13∪Y24])。由结论 2，可知再由结论 1，G[X1∪X2∪M],G[X3∪X4]都是空图，所以(G)≤ω(G[Y13∪Y24])+4≤ω(G)+4。如果 G[Y13]和 G[Y24]都是独立集和一条边的不交并，则有χ(G[X3∪X4])≤4。根据 ω(G)≥3，所以 χ(G)≤χ(G[X3∪X4])+4≤8≤ω(G)+5。

情况2t=1。

不妨设R1≠Ø，由结论4，得是完全图。根据结论3和命题1、命题2，可知G[R1∪Y13]是完美图。再由结论 1、结论2、结论 5，因此有

χ(G)≤χ(G[R1∪Y13])+5=ω(G[R1∪Y13])+5≤ω(G)-1+5=ω(G)+4。

情况3t=2。

由结论 4，不是一般性，设 R1≠Ø，R2≠Ø，则G[R1∪R2]是二部图的补图。根据结论5，可知都是空图。再根据命题2和结论1、结论2，有

χ(G)≤χ(G[R1∪R2])+6=ω(G[R1∪R2])+6≤ω(G)-2+6=ω(G)+4。

参考文献：

[1]GYÁRFÁS A.Problems from the world surrounding perfect graphs[J].Zastow Mat 1987,19(4)：413-441.

[2]RANDERATH B,SCHIERMEYER I.Vertex Colouring and Forbidden Subgraphs-A Survey [J].Graphs&Combinatorics,2004,20(1)：1-40.

[3]KOHL A,SCHIERMEYER I.Some results on Reed's Conjecture about ω, Δ and x with respect to α [J].Discrete Mathematics,2010,310(9)：1429-1438.

[4]WANG X,WU B.Upper bounds on the chromatic number of triangle-free graphs with a forbidden subtree[J].Journal of Combinatorial Optimization,2017,33：28-34.

[5]王晓.不含叉形图为导出子图的图的色数[J].华东师范大学学报,2016(1)：102-106.

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

[8]王晓.不含2K2为导出子图的图的染色[J].商洛学院学报,2015,29(2)：3-4.

[9]CHOUDUM S A,KARTHICK T,SHALU M A.Linear Chromatic Bounds for a Subfamily of 3K1-free Graphs[J].Graphs&Combinatorics,2008,24(5)：413-428.

[10]REINHARD D.Graph theory (Second Edition)[M].HongKong：Springer-Verlag,2000：2-25.

[11]CHUDNOVSKY M,ROBERTSON N,SEYMOUR P,et al.The Strong Perfect Graph Theorem [J].Annals of Mathematics,2006,164(1)：51-229.

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