禁用子图为C4和K1∪P4的图色数上界

王晓，卢晶

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

本文中所研究的图均为简单、无向、有限图，这里涉及到但未定义的概念可参阅文献[1]。设G是一个图，若存在一个映射c:V(G)→{1，2，3，…，k}使得对任意一条边uv缀E(G)都有c(u)≠c(v)，则c称是图G的一个k着色。图G的色数为满足k着色的最小的整数k，记为χ(G)。设U哿V(G)，则由顶点子集U和边子集EU={uv：u，v缀U，uv∈E(G)}所构成子图称为U的导出子图，记为G[U]。使得G[U]为完全图的顶点子集U称为图G的团，阶数最大的团称为G的最大团，最大团的阶数称为G的团数，记为ω(G)。如果对于图G任意一个导出子图H，都有χ(H)与ω(H)相等，则称图G为完美图。在完美图概念的基础上，Gyárfás[2]利用图团数的函数f(ω)来表示图的色数上界。由于对于任意图G都有χ(G)≥ω(G)，因此，完美图就是以f(x)=x为色数界的图类。Gyárfás[2]给出猜想：令F为一森林，则对于每一个不含F为导出子图的图G，都存在整数函数f(x,y)使得χ(G)≤f(F,ω(G))。关于此猜想的一些结论可参阅文献[3-7]。特别地，Wagon[6]证明了f(2K2,ω)≤(ω2+ω)/2；在文献[8]中，证明了f({2K2,C4},ω)≤ω+1；在文献[9]中,证明了f({2K2,K1+C4},ω)≤ω+5；其中2K2表示两条独立的边。

设G1和G2为两个图，它们的并图，记为G1∪G2，满足V(G1∪G2)=V(G1)∪V(G2)和E(G1∪G2)=E(G1)∪E(G2)；它们的联图，记为G1+G2，满足V(G1+G2)=V(G1)∪V(G2)和E(G1+G2)=E(G1∪G2)∪{xy|x缀V(G1),y缀V(G2)}。

本研究首先分析禁用子图为C4和K1∪P4（即不含C4和K1∪P4为导出子图）的图的结构，利用强完美图定理，得到了f(C4,K1∪P4},ω)≤2ω。再利用补图的性质，得到了f(2K2,K1＋P4},ω)≤ω＋1，此结果是对Wagon关于2K2结论的更为精细地刻画。

1 预备知识

设图G＝(V(G)，E(G)),其中V(G)和E(G)分别表示其顶点集和边集，边集E(G)为空集的图称为空图。设v∈V(G)，令NG(v)表示图G中v的所有邻点的集合。对于顶点子集V1，V2哿V(G)，用G[V1，V2]表示顶点集为V1∪V2，边集为{v1v2∈E(G):v1∈V1,v2∈V2}的子图。如果对于任意的v1∈V1,v2∈V2都有v1v2∈E(G[V1，V2])，则G[V1，V2]为完全二部图。图G的补图，记为，其中V()=V(G)且E()={uv：u，v∈V(G)，uv埸E(G)}。两个图G1和G2同构，记为G1艿G2。

图G中长度至少为5的导出圈称为G的洞，长度为奇数的洞称为奇洞。著名的强完美图定理[10-11]最先由Berge提出，最近由Seymour等证明。

定理1[10-11]图G是完美图当且仅当图G和其补图都不含奇洞。

显然，完全图是完美图。如果G是完美图，则其补图也是完美图。

引理1[12]若图G不含P4为导出子图，则G是完美图。

引理2 若图G1和G2是完美图，则联图G1+G2也是完美图。

证明 假设G1+G2中含有一个奇洞，设为Ck，其中k≥5。因为图G1和G2都是完美图，所以Ck既不是G1的子图也不是G2的子图，即1≤|V(Gi)∩V(Ck)|≤k-1(i=1,2)。因此，存在Gi使得|V(Gi)∩V(Ck)|≥3，不妨设为G1。对于u∈V(G2)∩V(Ck)，根据联图的定义，有|NG1+G2(u)∩V(G1)∩V(Ck)|≥3，这与Ck为导出圈矛盾。所以，G1+G2中不含奇洞。并且易知G1+G2的补图中也不含奇洞。由定理1，G1+G2也是完美图。

2 定理及其证明

定理2 设C4和K1∪P4是图G的禁用子图，则G为完美图或者G是连通的且存在顶点集的划分{V1,V1}使得G[V1]是一个完美图，G[V2]是一个完全图。

证明 因为K1∪P4是图G的禁用子图，所以不含长度大于等于的导出圈。再根据C4是图G的禁用子图，可知G的补图不含长度大于等于6的导出圈。由于C5的补图仍然是C5。因此，如果C5也是G的禁用子图，即G和其补图都不含奇洞，由定理1，可得G是一个完美图。假设G中存在一个长为5的圈为导出子图，设为C5，其中V(C5)={vi:i∈Z5}且vivi+1∈E(C5)，这里i∈Z5且运算都是在模5条件下的运算。

结论1 对任意的u∈V(G)V(C5)，令U=NG(u)∩V(C5)，则有G[U]∈{K2,P3,C5}。

当|U|=1时，不妨设U={v0}，则G[{u,v1,v2,v3,v4}]艿K1∪P4，矛盾。当|U|=2时，不妨设U={vi,vj}，则有vivj∈E(C5)，否则，存在vk∈V(C5)使得vivk，vjvk∈E(C5)，即，G[{u,vi，vk，vj}]艿C4，矛盾。当|U|=3时，U中必有两个顶点相邻，不妨设U={vi，vi+1，vj}，则有G[{vi，vi+1，vj}]艿P3，否则，vj=vi+3，即G[{u,vi+1，vi+2,vi+3}]艿C4，矛盾。当|U|=4时，不妨设vi埸U，则G[{u,vi-1,vi，vi+1}]艿C4，矛盾。当|U|=5时，即有G[U]=C5。综上，结论1成立。

由结论1，可知G是连通图。为了证明方便起见，令Ai={u∈V(G)V(C5):uvi,uvi+1∈E(G)}，Bi={u∈V(G)V(C5):uvi-1,uvi,uvi+1∈E(G)}，D={u∈V(G)V(C5):V(C5)哿NG(u)}，再由结论1，显然有

结论2 若Ai≠准，则Ai-2=准 且Ai+2=准。

设ui∈Ai，如果存在ui+2∈Ai+2，则uiui+2埸E(G)，否则G[{ui,ui+2,vi+1,vi+2}]艿C4，矛盾。然而，这样则有G[{vi-1,ui,vi+1,vi+2}]艿K1∪P4矛盾。因此，Ai+2=准。同理可得Ai-2=准。

结论3 若Ai≠准 且Ai+1≠准，则G[Ai∪Ai+1]为完全图。

设ui∈Ai,ui+1∈Ai+1。假设ui,ui+1埸E(G)，则有G[{ui,ui+1,vi+2,vi+3,vi+4}]艿K1∪P4，矛盾，所以G[Ai,Ai+1]是完全二部图。假设埸E(G)，结合E(G)，则有，矛盾，所以G[Ai]是完全图。同理可得G[Ai+1]是完全图。综上，G[Ai∪Ai+1]为完全图。

结论4G[Bi,Bi+2]是空图。

设ui∈Bi，ui+2∈Bi+2，如果uiui+2∈E(G)，则有G[{ui,ui+2,vi+3,vi+4}]艿C4，矛盾。因此，G[Bi,Bi+2]是空图。

结论5G[{vi}∪Bi∪D]是完全图。

设x,y∈Bi∪D，即有xvi，xvi-1,xvi+1,yvi-1,yvi+1∈E(G)，如果xy埸E(G)，则有G[{x，y，vi-1，vi+1}]艿C4，矛盾。所以，G[{vi}∪Bi∪D]是完全图。

结论6G[{vi，vi+1，vi+2，vi+3}∪Bi∪Bi+1∪Bi+2∪Bi+3]是完美图。

令Gi=G[{vi，vi+1，vi+2，vi+3}∪Bi∪Bi+1∪Bi+2∪Bi+3]，由结论4和结论5，可知Gi中不含C5为导出子图。又因为G和其补图中都不含长度至少是7的洞，因此，Gi为完美图。

结论7G[Ai∪Ai+1,Bi+1]是完全二部图。

设x∈Ai∪Ai+1,y∈Bi+1，如果xy埸E(G)，则当x∈Ai时有G[{x,y，vi+2，vi+3,vi+4}艿K1∪P4，当x∈Ai+1时有G[{x,y，vi，vi-1,vi-2}]艿K1∪P4，矛盾。因此，G[Ai∪Ai+1,Bi+1]是完全二部图。

根据结论2，最多有两个Ai不为空且是相邻的，不失一般性，设A2=A3=A4=准。

如果A0=A1=准，令V1={v0,v1,v2,v3}∪B0∪B1∪B2∪B3，V2={v4}∪B4∪D，由结论5和结论6，可知G[V1]是完美图，G[V2]是完全图。

如果A0≠准 且A1≠准，令V1={v0,v2,v3，v4}∪B0∪B2∪B3∪B4，V2={v1}∪A0∪A1∪B2∪D，由结论6，可知G[V1]是完美图，由结论3，结论5和结论7，可知G[V2]是完全图。

如果{A0，A1}中恰有一个为空集，不妨设A1=准且A0≠准。此时，若G[A0]为完全图，则令V1={v1,v2,v3，v4}∪B1∪B2∪B3∪B4，V2={v0}∪A0∪B0∪D，由结论6，可知G[V1]是完美图，由结论5和结论7，可知G[V2]是完全图。

设A1=A2=A3=A4=准，A0≠准 且G[A0]不是完全图。令a,b∈A0且ab埸E(G)，则有如下结论。

结论8G[A0,B4]为空图。

设x∈B4，y∈A0且xy∈E(G)，则必有对任意的z∈A0有xz∈E(G)，否则，当yz埸E(G)时，G[{z,y,x,v4，v2}]艿K1∪P4当yz∈E(G)时，G[{z,y,x,v3，v2}]艿K1∪P4矛盾。所以ax,bx∈E(G)，则有G[{a,b,x,v3，v2}]艿K1∪P4，矛盾。因此，G[A0,B4]为空图。

结论9G[B0,B1]和G[B0,B4]都是完全二部图。

设x∈B0，y∈B1且xy埸E(G)，由结论7，可知ax,ay,bx,by∈E(G)，即G[{a,b,x,y}]艿C4，矛盾。所以，G[B0,B1]是完全二部图。

设x∈B0，y∈B4且xy埸E(G)由结论8，可知，ay埸E(G)即有G[{a,y,v4,x,v2}]艿K1∪P4，矛盾。因此，G[B0,B4]是完全二部图。

结论10G[B2,B3]是完全二部图。

设x∈B2，y∈B3，则ay埸E(G)，否则，G[{a,y,v1,v2}]艿C4，矛盾。又由对称性和结论8，可知G[A0,B2]为空图，即ax埸E(G)。若xy埸E(G)，则G[{a,x,v2,y,v4}]艿K1∪P4，矛盾。因此，G[B2,B3]是完全二部图。

令V1={v0,v1,v4}∪A0∪B0∪B1∪B4，V2={v2,v3}∪B2∪B3∪D。G[A0]不含P4为导出子图，否则，G中含K1∪P4为其导出子图。根据引理1，G[A0]是完美图。由结论5，可知G[{v1}∪B1]和G[{v4}∪B4]都是完全图；再由结论4，结论7和结论8，可知G[{v1,v4}∪A0∪B1∪B4]不含C5为导出子图，即G[{v1,v4}∪A0∪B1∪B4]为完美图。又由结论5，可知G[{v0}∪B0]是完全图；再根据结论8和结论9，及引理2，可知G[V1]是完美图。由结论5和结论10可知，G[V2]是完全图。

定理3 设C4和K1∪P4是图G的禁用子图，则χ(G)≤2ω(G)。

证明 由定理2，G为完美图或者G是连通的且存在顶点集的划分{V1,V2}使得G[V1]是一个完美图，G[V2]是一个完全图。因此，若G为完美图，则有χ(G)=ω(G)；否则，χ(G)≤x(G[V1])+χ(G[V2])≤ω(G)+ω(G)=2ω(G)。

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

证明 由于2K2和K1+P4的补图分别为C4和K1∪P4，因此，图G的补图的禁用子图为C4和K1∪P4。根据定理2为完美图或者是连通的且存在顶点集的划分{V1,V2}使得[V1]是一个完美图[V2]是一个完全图。因此，若为完美图，则G也是完美图，即χ(G)=ω(G)；否则，G[V1]是一个完美图，G[V2]一个空图，即有χ(G)≤χ(G[V1])+χ(G[V2])≤ω(G)+1。