汪小黎，王曉

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

對(duì)于圖G的任一導(dǎo)出子圖H，如果其色數(shù)χ(H)與團(tuán)數(shù)ω(H)相等，則將圖G稱(chēng)為完美圖。在完美圖的基礎(chǔ)上，Gyárfás[1]提出了用函數(shù) f(ω)表示圖的色數(shù)上界的概念，完美圖就是以f(ω)=x為色數(shù)界的圖類(lèi)。對(duì)于給定的圖H，如果圖G不含與H同構(gòu)的導(dǎo)出子圖，則稱(chēng)H是圖G的禁用子圖或者圖 G是 H-free 的。在文獻(xiàn)[1]中，Gyárfás給出猜想：令F為一森林，則對(duì)于每一個(gè)F-free的圖G，都存在整數(shù)函數(shù) f(x,y)使得 χ(G)≤f(F,ω(G))。關(guān)于此猜想的一些結(jié)論可參閱文獻(xiàn)[2-6]。特別地，在文獻(xiàn)[7]中，Wagon 證明了 f(2K2,ω)≤(ω2+ω)/2；在文獻(xiàn)[8]中，證明了{(lán)2K2,C4,C5}-free的圖是完美圖，并且得到了 f({2K2,C4},ω)≤ω+1，其中 2K2表示兩條獨(dú)立的邊。

設(shè)G1和G2為兩個(gè)圖，它們的聯(lián)圖，記為G1+G2，表示滿足V(G1+G2)=V(G1)∪V(G2)和E(G1+G2)=E(G1)∪E(G2)∪{xy|x∈V(G1),y∈V(G2)}的圖。設(shè) 3K1表示三個(gè)獨(dú)立點(diǎn)，在文獻(xiàn)[9]中Choudum等給出f({3K1,K1+C4},ω)≤2ω。

本文考慮 {2K2,K1+C4}-free的圖的色數(shù)界函數(shù)，利用強(qiáng)完美圖定理，得到了f({2K2,K1+C4},ω)≤ω+5。

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

本文所研究的圖均為有限、簡(jiǎn)單、無(wú)向圖。對(duì)于圖G，其頂點(diǎn)集和邊集分別用V(G)和E(G)來(lái)表示。設(shè)V0?V(G)，則NG(V0)和G[V0]分別表示圖G中與V0中的某一個(gè)點(diǎn)相鄰且不在V0中的點(diǎn)的集合和由頂點(diǎn)子集V0導(dǎo)出的子圖。特別地，若V0={v}，則 NG(V0)可簡(jiǎn)寫(xiě)為 NG(v)。邊集 E(G)為空集的圖稱(chēng)為空?qǐng)D，若G[V0]為空?qǐng)D，則V0稱(chēng)為圖G的獨(dú)立集。其他文中涉及到的術(shù)語(yǔ)和符號(hào)可參考文獻(xiàn)[10]。

奇洞和補(bǔ)奇洞是完美圖定理中的兩個(gè)重要概念。圖G中長(zhǎng)度至少為5的導(dǎo)出奇圈稱(chēng)為G的奇洞，圖G的補(bǔ)圖中的奇洞的補(bǔ)圖稱(chēng)為原圖的G補(bǔ)奇洞。著名的完美圖定理[11-12]由Berge提出，Seymour等證明。

定理1圖G是完美圖當(dāng)且僅當(dāng)圖G是Berge圖，其中Berge圖是不含奇洞和補(bǔ)奇洞的圖。

與之等價(jià)的另外一種表述形式為：

定理2圖G是完美圖當(dāng)且僅當(dāng)圖G和其補(bǔ)圖都不含奇洞。

命題1設(shè)圖G存在一個(gè)頂點(diǎn)集的劃分V1,V2，使得G[V1]是完全圖，G[V2]是獨(dú)立集和一條邊的不交并，則圖G為完美圖。

證明設(shè)H是圖G的導(dǎo)出子圖，則有V(H)?V1或者V(H)?V2或者V(H)存在劃分V'1,V'2使得但是對(duì)任一奇洞，都不存在這三種情形，因此G不含奇洞。圖G的補(bǔ)圖存在頂點(diǎn)集的劃分U1,U2使得[U1]是完全圖刪掉一條邊所得的圖，是空?qǐng)D。同理可得，不含奇洞。根據(jù)定理2，即有圖G為完美圖。

如果圖G存在一個(gè)頂點(diǎn)集的劃分V1,V2，使得G[V1]是完全圖，G[V2]是獨(dú)立集，則稱(chēng)圖G是Split圖。一些常見(jiàn)的完美圖有：

命題2[11-12]Split圖、二部圖及其補(bǔ)圖都是完美圖。

在文獻(xiàn)[8]中，考慮了禁用子圖為2K2和C4的圖，得到：

定理3[8]設(shè)2K2和C4是圖G的禁用子圖，則有 χ(G)≤ω(G)+1。

2 定理及其證明

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

證明如果C4也是圖G的禁用子圖，則根據(jù)定理3，可知χ(G)≤ω(G)+1。因此，假設(shè)圖G含有C4做為其導(dǎo)出子圖。為后面的證明方便起見(jiàn)，令A(yù)=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。有如下結(jié)論。

結(jié)論 1X1∪X2∪M和 X3∪X4或者是空集或者是獨(dú)立集。

假設(shè) X1∪X2、M 和 X3∪X4都不是空集，因?yàn)?K2是圖G的禁用子圖，所以它們都是獨(dú)立集。如果存在 u∈X1∪X2，v∈M 使得 uu'∈E(G)，則有G[{u,u',v3,v4}]≌2K2，矛盾。因此 X1∪X2∪M 是獨(dú)立集。

結(jié)論2或者是空?qǐng)D或者是完全二部圖。

因?yàn)?K2是圖G的禁用子圖，所以，如果Yi(i+1)≠? 中，(i∈Z4)，則 Yi(i+1)是獨(dú)立集。對(duì)于 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，即或者是空?qǐng)D或者是完全二部圖。

結(jié)論 3若 Yi(i+2)≠?，(i∈Z4)，則 G[Yi(i+2)]或者是完全圖，或者是空?qǐng)D，或者是獨(dú)立集和一條邊的不交并。

不失一般性，假設(shè)Y13≠?且G[Y13]不是完全圖不是空?qǐng)D也不是獨(dú)立集和一條邊的不交并，則G[Y13]必然含有P3為其導(dǎo)出子圖，即有G[V(P3)∪{v1,v3}]≌K1+C4，矛盾。

結(jié)論 4若 Ri≠?,(i∈Z4)，則 G[Ri]是完全圖且 Ri+2=?。

假設(shè)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，當(dāng) riri+2∈E(G)時(shí)，有 G[{ri,ri+2,vi-1,vi,vi+1}]≌K1+C4，矛盾；當(dāng) riri+2?E(G)時(shí)，有 G[{ri,ri+2,vi,vi+2}]≌2K2，矛盾。因此有Ri+2=?。

結(jié)論 5若 Ri≠?(i∈Z4)，則 G[Y(i-1)(i+1)]為空?qǐng)D。

設(shè) ri∈Ri，u∈Y(i-1)(i+1)，則有 riu?E(G)，否則有 G[{ri,u,vi-1,vi,vi+1}]≌K1+C4，矛盾?，F(xiàn)假設(shè) u,u'∈Y(i-1)(i+1)且 uu'∈E(G)，則有 G[{u,u',ri,vi}]≌2K2，矛盾。因此G[Y(i-1)(i+1)]為空?qǐng)D。

根據(jù)結(jié)論 4，令 t=|{|Ri：Ri≠?,i∈Z4}|，則 t≤2。下面分三種情況來(lái)證明。

情況1t=0。

如果G[Y13]和G[Y24]都不是獨(dú)立集和一條邊的不交并，則由結(jié)論3，可知G[Y13∪Y24]或者是二部圖，或者是Split圖，或者是二部圖的補(bǔ)圖。根據(jù)命題2，可知G[Y13∪Y24]是完美圖。如果在G[Y13]和G[Y24]中，有一個(gè)是獨(dú)立集和一條邊的不交并，另一個(gè)是完全圖。根據(jù)命題1，可知G[Y13∪Y24]是完美圖。即 χ(G[Y13∪Y24])=ω(G[Y13∪Y24])。由結(jié)論 2，可知再由結(jié)論 1，G[X1∪X2∪M],G[X3∪X4]都是空?qǐng)D，所以(G)≤ω(G[Y13∪Y24])+4≤ω(G)+4。如果 G[Y13]和 G[Y24]都是獨(dú)立集和一條邊的不交并，則有χ(G[X3∪X4])≤4。根據(jù) ω(G)≥3，所以 χ(G)≤χ(G[X3∪X4])+4≤8≤ω(G)+5。

情況2t=1。

不妨設(shè)R1≠?，由結(jié)論4，得是完全圖。根據(jù)結(jié)論3和命題1、命題2，可知G[R1∪Y13]是完美圖。再由結(jié)論 1、結(jié)論2、結(jié)論 5，因此有

χ(G)≤χ(G[R1∪Y13])+5=ω(G[R1∪Y13])+5≤ω(G)-1+5=ω(G)+4。

情況3t=2。

由結(jié)論 4，不是一般性，設(shè) R1≠?，R2≠?，則G[R1∪R2]是二部圖的補(bǔ)圖。根據(jù)結(jié)論5，可知都是空?qǐng)D。再根據(jù)命題2和結(jié)論1、結(jié)論2，有

χ(G)≤χ(G[R1∪R2])+6=ω(G[R1∪R2])+6≤ω(G)-2+6=ω(G)+4。

參考文獻(xiàn)：

[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]王曉.不含叉形圖為導(dǎo)出子圖的圖的色數(shù)[J].華東師范大學(xué)學(xué)報(bào),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為導(dǎo)出子圖的圖的染色[J].商洛學(xué)院學(xué)報(bào),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]宋春偉.強(qiáng)完美圖定理及相關(guān)的問(wèn)題[J].數(shù)學(xué)進(jìn)展,2008,37(2)：153-162.