禁用子圖為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。