禁用子圖為C4和K1∪P4的圖色數(shù)上界

王曉，盧晶

（商洛學(xué)院數(shù)學(xué)與計(jì)算機(jī)應(yīng)用學(xué)院，陜西商洛726000）

本文中所研究的圖均為簡(jiǎn)單、無(wú)向、有限圖，這里涉及到但未定義的概念可參閱文獻(xiàn)[1]。設(shè)G是一個(gè)圖，若存在一個(gè)映射c:V(G)→{1，2，3，…，k}使得對(duì)任意一條邊uv綴E(G)都有c(u)≠c(v)，則c稱(chēng)是圖G的一個(gè)k著色。圖G的色數(shù)為滿足k著色的最小的整數(shù)k，記為χ(G)。設(shè)U哿V(G)，則由頂點(diǎn)子集U和邊子集EU={uv：u，v綴U，uv∈E(G)}所構(gòu)成子圖稱(chēng)為U的導(dǎo)出子圖，記為G[U]。使得G[U]為完全圖的頂點(diǎn)子集U稱(chēng)為圖G的團(tuán)，階數(shù)最大的團(tuán)稱(chēng)為G的最大團(tuán)，最大團(tuán)的階數(shù)稱(chēng)為G的團(tuán)數(shù)，記為ω(G)。如果對(duì)于圖G任意一個(gè)導(dǎo)出子圖H，都有χ(H)與ω(H)相等，則稱(chēng)圖G為完美圖。在完美圖概念的基礎(chǔ)上，Gyárfás[2]利用圖團(tuán)數(shù)的函數(shù)f(ω)來(lái)表示圖的色數(shù)上界。由于對(duì)于任意圖G都有χ(G)≥ω(G)，因此，完美圖就是以f(x)=x為色數(shù)界的圖類(lèi)。Gyárfás[2]給出猜想：令F為一森林，則對(duì)于每一個(gè)不含F(xiàn)為導(dǎo)出子圖的圖G，都存在整數(shù)函數(shù)f(x,y)使得χ(G)≤f(F,ω(G))。關(guān)于此猜想的一些結(jié)論可參閱文獻(xiàn)[3-7]。特別地，Wagon[6]證明了f(2K2,ω)≤(ω2+ω)/2；在文獻(xiàn)[8]中，證明了f({2K2,C4},ω)≤ω+1；在文獻(xiàn)[9]中,證明了f({2K2,K1+C4},ω)≤ω+5；其中2K2表示兩條獨(dú)立的邊。

設(shè)G1和G2為兩個(gè)圖，它們的并圖，記為G1∪G2，滿足V(G1∪G2)=V(G1)∪V(G2)和E(G1∪G2)=E(G1)∪E(G2)；它們的聯(lián)圖，記為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為導(dǎo)出子圖）的圖的結(jié)構(gòu)，利用強(qiáng)完美圖定理，得到了f(C4,K1∪P4},ω)≤2ω。再利用補(bǔ)圖的性質(zhì)，得到了f(2K2,K1＋P4},ω)≤ω＋1，此結(jié)果是對(duì)Wagon關(guān)于2K2結(jié)論的更為精細(xì)地刻畫(huà)。

1 預(yù)備知識(shí)

設(shè)圖G＝(V(G)，E(G)),其中V(G)和E(G)分別表示其頂點(diǎn)集和邊集，邊集E(G)為空集的圖稱(chēng)為空?qǐng)D。設(shè)v∈V(G)，令NG(v)表示圖G中v的所有鄰點(diǎn)的集合。對(duì)于頂點(diǎn)子集V1，V2哿V(G)，用G[V1，V2]表示頂點(diǎn)集為V1∪V2，邊集為{v1v2∈E(G):v1∈V1,v2∈V2}的子圖。如果對(duì)于任意的v1∈V1,v2∈V2都有v1v2∈E(G[V1，V2])，則G[V1，V2]為完全二部圖。圖G的補(bǔ)圖，記為，其中V()=V(G)且E()={uv：u，v∈V(G)，uv埸E(G)}。兩個(gè)圖G1和G2同構(gòu)，記為G1艿G2。

圖G中長(zhǎng)度至少為5的導(dǎo)出圈稱(chēng)為G的洞，長(zhǎng)度為奇數(shù)的洞稱(chēng)為奇洞。著名的強(qiáng)完美圖定理[10-11]最先由Berge提出，最近由Seymour等證明。

定理1[10-11]圖G是完美圖當(dāng)且僅當(dāng)圖G和其補(bǔ)圖都不含奇洞。

顯然，完全圖是完美圖。如果G是完美圖，則其補(bǔ)圖也是完美圖。

引理1[12]若圖G不含P4為導(dǎo)出子圖，則G是完美圖。

引理2 若圖G1和G2是完美圖，則聯(lián)圖G1+G2也是完美圖。

證明 假設(shè)G1+G2中含有一個(gè)奇洞，設(shè)為Ck，其中k≥5。因?yàn)閳DG1和G2都是完美圖，所以Ck既不是G1的子圖也不是G2的子圖，即1≤|V(Gi)∩V(Ck)|≤k-1(i=1,2)。因此，存在Gi使得|V(Gi)∩V(Ck)|≥3，不妨設(shè)為G1。對(duì)于u∈V(G2)∩V(Ck)，根據(jù)聯(lián)圖的定義，有|NG1+G2(u)∩V(G1)∩V(Ck)|≥3，這與Ck為導(dǎo)出圈矛盾。所以，G1+G2中不含奇洞。并且易知G1+G2的補(bǔ)圖中也不含奇洞。由定理1，G1+G2也是完美圖。

2 定理及其證明

定理2 設(shè)C4和K1∪P4是圖G的禁用子圖，則G為完美圖或者G是連通的且存在頂點(diǎn)集的劃分{V1,V1}使得G[V1]是一個(gè)完美圖，G[V2]是一個(gè)完全圖。

證明 因?yàn)镵1∪P4是圖G的禁用子圖，所以不含長(zhǎng)度大于等于的導(dǎo)出圈。再根據(jù)C4是圖G的禁用子圖，可知G的補(bǔ)圖不含長(zhǎng)度大于等于6的導(dǎo)出圈。由于C5的補(bǔ)圖仍然是C5。因此，如果C5也是G的禁用子圖，即G和其補(bǔ)圖都不含奇洞，由定理1，可得G是一個(gè)完美圖。假設(shè)G中存在一個(gè)長(zhǎng)為5的圈為導(dǎo)出子圖，設(shè)為C5，其中V(C5)={vi:i∈Z5}且vivi+1∈E(C5)，這里i∈Z5且運(yùn)算都是在模5條件下的運(yùn)算。

結(jié)論1 對(duì)任意的u∈V(G)V(C5)，令U=NG(u)∩V(C5)，則有G[U]∈{K2,P3,C5}。

當(dāng)|U|=1時(shí)，不妨設(shè)U={v0}，則G[{u,v1,v2,v3,v4}]艿K1∪P4，矛盾。當(dāng)|U|=2時(shí)，不妨設(shè)U={vi,vj}，則有vivj∈E(C5)，否則，存在vk∈V(C5)使得vivk，vjvk∈E(C5)，即，G[{u,vi，vk，vj}]艿C4，矛盾。當(dāng)|U|=3時(shí)，U中必有兩個(gè)頂點(diǎn)相鄰，不妨設(shè)U={vi，vi+1，vj}，則有G[{vi，vi+1，vj}]艿P3，否則，vj=vi+3，即G[{u,vi+1，vi+2,vi+3}]艿C4，矛盾。當(dāng)|U|=4時(shí)，不妨設(shè)vi埸U，則G[{u,vi-1,vi，vi+1}]艿C4，矛盾。當(dāng)|U|=5時(shí)，即有G[U]=C5。綜上，結(jié)論1成立。

由結(jié)論1，可知G是連通圖。為了證明方便起見(jiàn)，令A(yù)i={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)}，再由結(jié)論1，顯然有

結(jié)論2 若Ai≠準(zhǔn)，則Ai-2=準(zhǔn) 且Ai+2=準(zhǔn)。

設(shè)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=準(zhǔn)。同理可得Ai-2=準(zhǔn)。

結(jié)論3 若Ai≠準(zhǔn) 且Ai+1≠準(zhǔn)，則G[Ai∪Ai+1]為完全圖。

設(shè)ui∈Ai,ui+1∈Ai+1。假設(shè)ui,ui+1埸E(G)，則有G[{ui,ui+1,vi+2,vi+3,vi+4}]艿K1∪P4，矛盾，所以G[Ai,Ai+1]是完全二部圖。假設(shè)埸E(G)，結(jié)合E(G)，則有，矛盾，所以G[Ai]是完全圖。同理可得G[Ai+1]是完全圖。綜上，G[Ai∪Ai+1]為完全圖。

結(jié)論4G[Bi,Bi+2]是空?qǐng)D。

設(shè)ui∈Bi，ui+2∈Bi+2，如果uiui+2∈E(G)，則有G[{ui,ui+2,vi+3,vi+4}]艿C4，矛盾。因此，G[Bi,Bi+2]是空?qǐng)D。

結(jié)論5G[{vi}∪Bi∪D]是完全圖。

設(shè)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]是完全圖。

結(jié)論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]，由結(jié)論4和結(jié)論5，可知Gi中不含C5為導(dǎo)出子圖。又因?yàn)镚和其補(bǔ)圖中都不含長(zhǎng)度至少是7的洞，因此，Gi為完美圖。

結(jié)論7G[Ai∪Ai+1,Bi+1]是完全二部圖。

設(shè)x∈Ai∪Ai+1,y∈Bi+1，如果xy埸E(G)，則當(dāng)x∈Ai時(shí)有G[{x,y，vi+2，vi+3,vi+4}艿K1∪P4，當(dāng)x∈Ai+1時(shí)有G[{x,y，vi，vi-1,vi-2}]艿K1∪P4，矛盾。因此，G[Ai∪Ai+1,Bi+1]是完全二部圖。

根據(jù)結(jié)論2，最多有兩個(gè)Ai不為空且是相鄰的，不失一般性，設(shè)A2=A3=A4=準(zhǔn)。

如果A0=A1=準(zhǔn)，令V1={v0,v1,v2,v3}∪B0∪B1∪B2∪B3，V2={v4}∪B4∪D，由結(jié)論5和結(jié)論6，可知G[V1]是完美圖，G[V2]是完全圖。

如果A0≠準(zhǔn) 且A1≠準(zhǔn)，令V1={v0,v2,v3，v4}∪B0∪B2∪B3∪B4，V2={v1}∪A0∪A1∪B2∪D，由結(jié)論6，可知G[V1]是完美圖，由結(jié)論3，結(jié)論5和結(jié)論7，可知G[V2]是完全圖。

如果{A0，A1}中恰有一個(gè)為空集，不妨設(shè)A1=準(zhǔn)且A0≠準(zhǔn)。此時(shí)，若G[A0]為完全圖，則令V1={v1,v2,v3，v4}∪B1∪B2∪B3∪B4，V2={v0}∪A0∪B0∪D，由結(jié)論6，可知G[V1]是完美圖，由結(jié)論5和結(jié)論7，可知G[V2]是完全圖。

設(shè)A1=A2=A3=A4=準(zhǔn)，A0≠準(zhǔn) 且G[A0]不是完全圖。令a,b∈A0且ab埸E(G)，則有如下結(jié)論。

結(jié)論8G[A0,B4]為空?qǐng)D。

設(shè)x∈B4，y∈A0且xy∈E(G)，則必有對(duì)任意的z∈A0有xz∈E(G)，否則，當(dāng)yz埸E(G)時(shí)，G[{z,y,x,v4，v2}]艿K1∪P4當(dāng)yz∈E(G)時(shí)，G[{z,y,x,v3，v2}]艿K1∪P4矛盾。所以ax,bx∈E(G)，則有G[{a,b,x,v3，v2}]艿K1∪P4，矛盾。因此，G[A0,B4]為空?qǐng)D。

結(jié)論9G[B0,B1]和G[B0,B4]都是完全二部圖。

設(shè)x∈B0，y∈B1且xy埸E(G)，由結(jié)論7，可知ax,ay,bx,by∈E(G)，即G[{a,b,x,y}]艿C4，矛盾。所以，G[B0,B1]是完全二部圖。

設(shè)x∈B0，y∈B4且xy埸E(G)由結(jié)論8，可知，ay埸E(G)即有G[{a,y,v4,x,v2}]艿K1∪P4，矛盾。因此，G[B0,B4]是完全二部圖。

結(jié)論10G[B2,B3]是完全二部圖。

設(shè)x∈B2，y∈B3，則ay埸E(G)，否則，G[{a,y,v1,v2}]艿C4，矛盾。又由對(duì)稱(chēng)性和結(jié)論8，可知G[A0,B2]為空?qǐng)D，即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為導(dǎo)出子圖，否則，G中含K1∪P4為其導(dǎo)出子圖。根據(jù)引理1，G[A0]是完美圖。由結(jié)論5，可知G[{v1}∪B1]和G[{v4}∪B4]都是完全圖；再由結(jié)論4，結(jié)論7和結(jié)論8，可知G[{v1,v4}∪A0∪B1∪B4]不含C5為導(dǎo)出子圖，即G[{v1,v4}∪A0∪B1∪B4]為完美圖。又由結(jié)論5，可知G[{v0}∪B0]是完全圖；再根據(jù)結(jié)論8和結(jié)論9，及引理2，可知G[V1]是完美圖。由結(jié)論5和結(jié)論10可知，G[V2]是完全圖。

定理3 設(shè)C4和K1∪P4是圖G的禁用子圖，則χ(G)≤2ω(G)。

證明 由定理2，G為完美圖或者G是連通的且存在頂點(diǎn)集的劃分{V1,V2}使得G[V1]是一個(gè)完美圖，G[V2]是一個(gè)完全圖。因此，若G為完美圖，則有χ(G)=ω(G)；否則，χ(G)≤x(G[V1])+χ(G[V2])≤ω(G)+ω(G)=2ω(G)。

定理4 設(shè)2K2和K1+P4是圖G的禁用子圖，則χ(G)≤ω(G)+1。

證明 由于2K2和K1+P4的補(bǔ)圖分別為C4和K1∪P4，因此，圖G的補(bǔ)圖的禁用子圖為C4和K1∪P4。根據(jù)定理2為完美圖或者是連通的且存在頂點(diǎn)集的劃分{V1,V2}使得[V1]是一個(gè)完美圖[V2]是一個(gè)完全圖。因此，若為完美圖，則G也是完美圖，即χ(G)=ω(G)；否則，G[V1]是一個(gè)完美圖，G[V2]一個(gè)空?qǐng)D，即有χ(G)≤χ(G[V1])+χ(G[V2])≤ω(G)+1。