不含3K1+K2 和C4 為導出子圖的圖的色數

王 曉，汪小黎

WANG Xiao,WANG Xiaoli

商洛學院 數學與計算機應用學院，陜西 商洛726000

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

1 引言

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

定理1[4-5]（強完美圖定理）圖G是完美圖當且僅當圖G是Berge圖。

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

任意給定圖H，如果圖G不含與H同構的圖為導出子圖，則稱圖G是H-free（不含H為導出子圖）的。在文獻[6]中Gyárfás給出如下猜想：

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

設3K1+K2表示3 個獨立點和一條獨立邊，這里考慮不含3K1+K2和C4作為導出子圖的圖的色數。通過對這類圖的獨立數進行分類討論，得到了關于團數的線性函數表達式的色數的上界。

2 主要結論及證明

Berge 圖為不含奇洞和補奇洞的圖，不含補奇洞即其補圖不含奇洞，所以圖G為Berge 圖當且僅當G和-G都不含奇洞。

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

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

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

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

如果圖G的頂點集V(G)能劃分成獨立集和團的并，則稱圖G是Split 圖。顯然Split 圖是二部圖的補圖，所以Split圖是完美圖。

定理2設圖G是不含3K1+K2和C4為導出子圖的圖，則有：

（1）當α(G)=1 或α(G)≥6 時，有χ(G)=ω(G)；

（2）當α(G)=2 時，有χ(G)≤2ω(G)；

（3）當α(G)=3 時，有χ(G)≤3ω(G)；

（4）當α(G)=4 時，有χ(G)≤4ω(G)；

（5）當α(G)=5 時，有χ(G)≤2ω(G)+1。

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

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

情形2|S|=2 即α(G)=2。設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]都是完全圖；否則，假設存在兩個頂點x,y∈A但xy?E(G)，則有G[{x,y,u,v}]?C4，矛盾；若存在x,y∈B但xy?E(G)則{v,x,y}是獨立集，與α(G)=2 矛盾，同理G[C]也是完全圖。所以G[A∪B]是二部圖的補圖，G[C∪{u,v}]是Split 圖，即G[A∪B]和G[C∪{u,v}]都是完美圖，因此有χ(G)≤2ω(G)。

情形3|S|=3 即α(G)=3。設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構成V(G)的一個劃分，有如下結論：

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

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

結論2G[B12∪B13∪B23]是完美圖。

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

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

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

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

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

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

情形4|S|=4 即α(G)=4。設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構成V(G)的一個劃分。則有下面結論。

結論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]都是完全圖。

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

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

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

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

設M=G[C123∪C124∪C134∪C234]，若M中含C5作為導出子圖，設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作為導出子圖，矛盾。因此M不含C5和C7作為導出子圖，由結論5 和引理3，所以M是完美圖。

結論8G[B14∪D∪S]是完美圖。

假 設 存 在 頂 點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圖，即為完美圖。

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

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

所以在|A1∩A2|,|A1∩A3|,|A2∩A3|中至少有一個大于等于2，不 妨 設|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 證畢。

本文的主要結論定理2 得到了一類圖的團數有關的色數的上界，并且當獨立數大于等于6 時這類圖是完美圖，部分地回答了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] 宋春偉.強完美圖定理及相關問題[J].數學進展，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作為導出子圖的圖的色數[J].華東師范大學學報：自然科學版，2014（1）：9-12.

[14] 王曉，張東翰.不含HVN 和C4為導出子圖的圖的色數[J].河南科學，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.