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