王 曉，汪小黎

WANG Xiao,WANG Xiaoli

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

College of Mathematics and Computer Application,Shangluo University,Shangluo,Shannxi 726000

1 引言

本文所研究的圖均為有限、無向、簡單圖。設(shè)G=(V(G),E(G))表示一個(gè)圖，其中V(G)和E(G)分別表示圖G的頂點(diǎn)集和邊集。給定v∈V(G)和A?V(G)，NG(v)和G[A]分別表示圖G中v的鄰點(diǎn)集和由A導(dǎo)出的子圖。設(shè)α(G)、ω(G)、χ(G)分別表示圖G的獨(dú)立數(shù)，團(tuán)數(shù)和頂點(diǎn)色數(shù)[1]（簡稱為色數(shù)）。顯然有χ(G)≥ω(G)，并且由文獻(xiàn)[2-3]中Erdos 的經(jīng)典結(jié)論，可知圖的色數(shù)和團(tuán)數(shù)之差χ(G)-ω(G)可以任意大。一個(gè)圖G稱為完美圖，如果對于圖G的任意導(dǎo)出子圖H，都有χ(H)=ω(H)。完美圖的概念應(yīng)用廣泛，信息論里的Shannon Capacity與其密切相關(guān)：一個(gè)圖的Shannon Capacity 總是介于團(tuán)數(shù)和色數(shù)之間，所以完美圖的Shannon Capacity 就被這兩個(gè)參數(shù)中的任何一個(gè)確定了。法國數(shù)學(xué)家Berge 于1961 年提出的強(qiáng)完美圖猜想已被Seymour 等4 位數(shù)學(xué)家證明[4-5]。設(shè)H是圖G的導(dǎo)出子圖，若H是長度至少為5 的奇圈，則稱H為G的奇洞；若H是長至少為5的奇圈的補(bǔ)圖，則稱H為G的補(bǔ)奇洞。不含奇洞和補(bǔ)奇洞的圖稱為Berge圖。

定理1[4-5]（強(qiáng)完美圖定理）圖G是完美圖當(dāng)且僅當(dāng)圖G是Berge圖。

Gyárfás 推廣了完美圖的概念，給出用團(tuán)數(shù)的函數(shù)來表示圖的色數(shù)上界的概念[6]：對于任意的圖G∈Φ，如果存在關(guān)于團(tuán)數(shù)的整數(shù)函數(shù)f使得χ(G)≤f(ω(G))，則稱Φ是關(guān)于f為色數(shù)界的圖類。顯然，以f(x)=x為色數(shù)界的圖類就是完美圖。

任意給定圖H，如果圖G不含與H同構(gòu)的圖為導(dǎo)出子圖，則稱圖G是H-free（不含H為導(dǎo)出子圖）的。在文獻(xiàn)[6]中Gyárfás給出如下猜想：

猜想1[6]設(shè)F是一個(gè)森林，對于每一個(gè)F-free 的圖G，存在整數(shù)函數(shù)f(F,ω(G)) 使得χ(G)≤f(F,ω(G))。

設(shè)3K1+K2表示3 個(gè)獨(dú)立點(diǎn)和一條獨(dú)立邊，這里考慮不含3K1+K2和C4作為導(dǎo)出子圖的圖的色數(shù)。通過對這類圖的獨(dú)立數(shù)進(jìn)行分類討論，得到了關(guān)于團(tuán)數(shù)的線性函數(shù)表達(dá)式的色數(shù)的上界。

2 主要結(jié)論及證明

Berge 圖為不含奇洞和補(bǔ)奇洞的圖，不含補(bǔ)奇洞即其補(bǔ)圖不含奇洞，所以圖G為Berge 圖當(dāng)且僅當(dāng)G和-G都不含奇洞。

引理1設(shè)圖G不含長度介于5到2k-1之間的奇洞且不含C4作為導(dǎo)出子圖，如果圖G的頂點(diǎn)集V(G)存在一個(gè)劃分A1,A2,…,Ak滿足每個(gè)G[Ai](i=1,2,…,k)都是完全圖，則G是完美圖。

證明由每一個(gè)G[Ai](i=1,2,…,k)都是完全圖，所以G不含長度大于等于2k+1 的導(dǎo)出圈，又G不含長度介于5 到2k-1 之間的奇洞，因此G中不含奇洞。

另一方面，若G的補(bǔ)圖含有C5為導(dǎo)出子圖，由于，所以G含有C5為導(dǎo)出子圖，矛盾。若中含有長度大于5的奇洞，設(shè)為Cm(m≥7)，則存在M={v1,v2,u1,u2}?V(Cm)使得，因而，即圖G含有C4作為導(dǎo)出子圖，矛盾。因此，圖G的補(bǔ)圖不含奇洞。

由定理1，所以圖G是完美圖。引理證畢。

如果圖G的頂點(diǎn)集V(G)能劃分成獨(dú)立集和團(tuán)的并，則稱圖G是Split 圖。顯然Split 圖是二部圖的補(bǔ)圖，所以Split圖是完美圖。

定理2設(shè)圖G是不含3K1+K2和C4為導(dǎo)出子圖的圖，則有：

（1）當(dāng)α(G)=1 或α(G)≥6 時(shí)，有χ(G)=ω(G)；

（2）當(dāng)α(G)=2 時(shí)，有χ(G)≤2ω(G)；

（3）當(dāng)α(G)=3 時(shí)，有χ(G)≤3ω(G)；

（4）當(dāng)α(G)=4 時(shí)，有χ(G)≤4ω(G)；

（5）當(dāng)α(G)=5 時(shí)，有χ(G)≤2ω(G)+1。

證明設(shè)S是圖G中的階數(shù)最大的獨(dú)立集，對?v∈V(G)S有|NG(v)∩S|≥1。顯然，當(dāng)|S|=1 時(shí)，即α(G)=1，圖G為完全圖，則有χ(G)=ω(G)。下面對圖G的獨(dú)立數(shù)，即S的階數(shù)，分5 種情形進(jìn)行討論。

情形1|S|≥6 即α(G)≥6。對于x∈V(G)S，令A(yù)x=NG(x)∩S，因?yàn)閳DG不含3K1+K2為導(dǎo)出子圖，所以|Ax|≥|S|-2。為了證明G是Split 圖只需證明G-S是一個(gè)團(tuán)。否則，假設(shè)存在x,y∈V(G)S，但xy?E(G)，則有|Ax∩Ay|≥|Ax|+|Ay|-|S|≥|S|-4 ≥2，即x,y在S中至少有兩個(gè)公共的鄰點(diǎn)u,v，則G[{x,y,u,v}]?C4，矛盾。所以G-S是一個(gè)團(tuán)，即圖G是Split 圖，因此圖G是完美圖，有χ(G)=ω(G)。

情形2|S|=2 即α(G)=2。設(shè)S={u,v}，A=NG(u)∩NG(v)，B=NG(u)NG(v)，C=NG(v)NG(u)，則S,A,B,C是V(G)的劃分并且G[A]、G[B]、G[C]都是完全圖；否則，假設(shè)存在兩個(gè)頂點(diǎn)x,y∈A但xy?E(G)，則有G[{x,y,u,v}]?C4，矛盾；若存在x,y∈B但xy?E(G)則{v,x,y}是獨(dú)立集，與α(G)=2 矛盾，同理G[C]也是完全圖。所以G[A∪B]是二部圖的補(bǔ)圖，G[C∪{u,v}]是Split 圖，即G[A∪B]和G[C∪{u,v}]都是完美圖，因此有χ(G)≤2ω(G)。

情形3|S|=3 即α(G)=3。設(shè)S={u1,u2,u3}，Ai=NG(ui)[NG(uj)∪NG(uk)]，Bij=[NG(ui)∩NG(uj)]NG(uk)，C=NG(ui)∩NG(uj)∩NG(uk)，其 中i,j,k∈{1,2,3} 且i,j,k兩兩互不相等，則S，A1,A2,A3，B12,B13,B23，C構(gòu)成V(G)的一個(gè)劃分，有如下結(jié)論：

結(jié)論1G[A1],G[A2],G[A3],G[B12],G[B13],G[B23],G[C]都是完全圖。

否則，若存在頂點(diǎn)x,y∈Ai(i=1,2,3)但xy?E(G)，則{x,y,uj,uk}(j≠i,k≠i) 是獨(dú)立集，與α(G)=3 矛盾；若 存 在 頂 點(diǎn)x,y∈Bij或x,y∈C但xy?E(G)，則G[{x,y,ui,uj}]?C4，矛盾。

結(jié)論2G[B12∪B13∪B23]是完美圖。

若G[B12∪B13∪B23]中含有C5作為導(dǎo)出子圖，設(shè)V(C5)={v1,v2,v3,v4,v5}，vivi+1∈E(G)(i=1,2,3,4) 且v5v1∈E(G)。同時(shí)不失一般性，令v1∈B13，v2,v3∈B12，v4,v5∈B23，則有G[{v1,v2,u2,v5}]?C4，矛盾。因此G[B12∪B13∪B23]中不含C5和C4作為導(dǎo)出子圖，由結(jié)論1 和引理1，可知G[B12∪B13∪B23]是完美圖。

結(jié)論3G[A1∪A2∪{u1,u2}]是完美圖。

由結(jié)論1，G[A1]和G[A2]都是完全圖，A1中的所有點(diǎn)都與u1相連，A2中的所有點(diǎn)都與u2相連，所以G[A1∪{u1}]和G[A2∪{u2}]也是完全圖。因此G[A1∪A2∪{u1,u2}]是二部圖的補(bǔ)圖，即為完美圖。

結(jié)論4G[A3∪C∪{u3}]是完美圖。

由G[A3∪{u3}] 和G[C] 都 是 完 全 圖，所 以G[A3∪C∪{u3}]是二部圖的補(bǔ)圖，即為完美圖。

綜合結(jié)論2、3、4，即有χ(G)≤3ω(G)。

情形4|S|=4 即α(G)=4。設(shè)S={u1,u2,u3,u4}，Ai=NG(ui)[NG(uj)∪NG(uk)∪NG(uh)]，Bij=[NG(ui)∩NG(uj)][NG(uk)∪NG(uh)，Cijk=[NG(ui)∩NG(uj)∩NG(uk)]NG(uh)，D=NG(ui) ∩NG(uj) ∩NG(uk) ∩NG(uh)，其 中i,j,k,h∈{1,2,3,4}且i,j,k,h兩兩互不相等，則S，A1,A2,A3,A4，B12,B13,B14,B23,B24,B34，C123,C124,C134,C234，D構(gòu)成V(G)的一個(gè)劃分。則有下面結(jié)論。

結(jié)論5A1=A2=A3=A4=?，且G[B12]，G[B13]，G[B14]，G[B23]，G[B24]，G[B34]，G[C123]，G[C124]，G[C134]，G[C234]，G[D]都是完全圖。

若存在頂點(diǎn)x∈Ai(i=1,2,3,4)，則有G[{x,u1,u2,u3,u4}]?3K1+K2，矛盾。類似于結(jié)論1 的證明，易得B12,B13,B14,B23,B24,B34，C123，C124，C134，C234和D的導(dǎo)出子圖都是完全圖。

結(jié)論6G[B12∪B13]和G[B23∪B24∪B34]都是完美圖。

由結(jié)論5，G[B12]，G[B13]，G[B23]，G[B24]，G[B34]為完全圖，所以G[B12∪B13]是二部圖的補(bǔ)圖，即為完美圖。對于G[B23∪B24∪B34]類似于結(jié)論2，所以也是完美圖。

結(jié)論7G[C123∪C124∪C134∪C234]是完美圖。

設(shè)M=G[C123∪C124∪C134∪C234]，若M中含C5作為導(dǎo)出子圖，設(shè)V(C5)={v1,v2,v3,v4,v5}，vivi+1∈E(G)(i=1,2,3,4)且v5v1∈E(G)。不失一般性，令v1,v2∈C123，v3∈C134，v4∈C234，v5∈C124，則G[{v1,u2,v4,u3}]?C4，矛盾。若M中含C7，同理可得M含有C4作為導(dǎo)出子圖，矛盾。因此M不含C5和C7作為導(dǎo)出子圖，由結(jié)論5 和引理3，所以M是完美圖。

結(jié)論8G[B14∪D∪S]是完美圖。

假 設(shè) 存 在 頂 點(diǎn)x∈B14，y∈D但xy?E(G)，則G[{x,u1,y,u4}]?C4，矛盾。又由于G[B14]和G[D]是完全圖，所以G[B14∪D]是完全圖。因此G[B14∪D∪S]是Split圖，即為完美圖。

綜合結(jié)論5～8，得χ(G)≤4ω(G)。

情形5|S|=5 即α(G)=5。此時(shí)，有α(G-S)≤2；否則，假設(shè)存在頂點(diǎn)v1,v2,v3∈V(G)S使得{v1,v2,v3}是獨(dú)立 集，令A(yù)k=NG(vk)∩S(k=1,2,3)，由 于 圖G不 含3K1+K2為導(dǎo)出子圖，所以|Ak|≥3。即有：

所以在|A1∩A2|,|A1∩A3|,|A2∩A3|中至少有一個(gè)大于等于2，不 妨 設(shè)|A1∩A2|≥2。故 存 在x,y∈A1∩A2使 得G[{x,y,v1,v2}]?C4，矛盾。

如果α(G-S)=1，則G-S是完全圖，即圖G是Split圖，所以χ(G)=ω(G)。

如果α(G-S)=2，由情形2，可知χ(G-S)≤2ω(G-S)，所以χ(G)≤2ω(G)+1。

定理4 證畢。

本文的主要結(jié)論定理2 得到了一類圖的團(tuán)數(shù)有關(guān)的色數(shù)的上界，并且當(dāng)獨(dú)立數(shù)大于等于6 時(shí)這類圖是完美圖，部分地回答了Gyárfás猜想。

[1] Reinhard D.Graph theory[M].2nd ed.Hong Kong，China：Springer-Verlag，2000.

[2] Erdos P.Graph theory and probability[J].Canad J Math，1959，11：34-38.

[3] Reed B.ω，Δ andχ[J].Journal of Graph Theory，1998，374：177-212.

[4] Chudnovsky M，Robertson N，Seymour P.The strong perfect graph theorem[J].Annals of Mathematics，2006，164：51-229.

[5] 宋春偉.強(qiáng)完美圖定理及相關(guān)問題[J].數(shù)學(xué)進(jìn)展，2008，37（2）：153-163.

[6] Gyárfás A.Problems from the world surrounding perfect graphs[J].Zastow Mat，1987，19：413-441.

[7] Wagon S.A bound on the chromatic number of graphs without certain induced subgraphs[J].Journal of Combin Theory：Series B，1980，29：345-346.

[8] Hoang C T，McDiarmid C.On the divisibility of graphs[J].Discrete Math，2002，242：145-156.

[9] Fan G，Xu B，Ye T，et al.Forbidden subgraphs and 3-coloring[J].Siam J Disc Math，2014，28：1226-1256.

[10] Randerath B，Schiermeyer I.A note on brooks theorem for triangle-free graphs[J].Australas J Comb，2002，26：3-9.

[11] Randerath B，Schiermeyer I.Vertex coloring and forbidden subgraphs—a survey[J].Graphs Combin，2004，20：1-40.

[12] Brandt S.Triangle-free graphs and forbidden subgraphs[J].Discrete Apply Math，2002，120：25-33.

[13] 段芳，張維娟.不含2K1+K2和C4作為導(dǎo)出子圖的圖的色數(shù)[J].華東師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2014（1）：9-12.

[14] 王曉，張東翰.不含HVN 和C4為導(dǎo)出子圖的圖的色數(shù)[J].河南科學(xué)，2015，33（3）：333-335.

[15] Randerath B.The Vizing bound for the chromatic number based on forbidden pairs[D].RWTH Aachen，1998.

[16] Duan Fuan，Wu B.Y.On chromatic number of graphs without certain induced subgraphs[J].Ars Combinatoria，2011（7）：33-44.