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

2019-02-21 01:41王晓卢晶
商洛学院学报 2019年2期
关键词:子图子集顶点

王晓,卢晶

(商洛学院数学与计算机应用学院,陕西商洛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。

猜你喜欢
子图子集顶点
拓扑空间中紧致子集的性质研究
过非等腰锐角三角形顶点和垂心的圆的性质及应用(下)
过非等腰锐角三角形顶点和垂心的圆的性质及应用(上)
关于2树子图的一些性质
关于奇数阶二元子集的分离序列
临界完全图Ramsey数
不含3K1和K1+C4为导出子图的图色数上界∗
完全二部图K6,n(6≤n≤38)的点可区别E-全染色
每一次爱情都只是爱情的子集
图G(p,q)的生成子图的构造与计数