不含2K2為導出子圖的圖的染色

王曉

（商洛學院數(shù)學與計算機應用學院，陜西商洛726000）

不含2K2為導出子圖的圖的染色

王曉

（商洛學院數(shù)學與計算機應用學院，陜西商洛726000）

利用強完美圖定理，得到不含{2K2、C4、C5}為導出子圖的圖是完美圖。進而證明了每一個不含{2K2、C4}為導出子圖的圖是(ω(G)+1)可著色的，并且給出一類滿足不含{2K2、C4}為導出子圖且χ(G)=ω(G)+1的圖類，其中ω(G)和χ(G)分別為圖G的團數(shù)和色數(shù)。

色數(shù)；團數(shù)；導出子圖

設χ(G)，ω(G)分別表示圖G的頂點色數(shù)和團數(shù)，顯然對于任一圖G，有χ(G)≥ω(G)[1]，且由文獻[2-3]中Erdos的經(jīng)典結論，可知圖的色數(shù)和團數(shù)之差χ(G)-ω(G)可以任意大。若對于G的任意導出子圖H都有χ(H)≥ω(H)，則稱圖G為完美圖，Berge提出的著名的完美圖猜想最近已由Seymour等四位數(shù)學家證明[4-5]。Gyárfás在完美圖的基礎上，提出了與團數(shù)有關的圖的色數(shù)上界的概念[6]，對于任意的圖G∈Φ，如果存在整數(shù)函數(shù)f使得χ(G)≤f(ω(G))，則稱Φ是關于f為色數(shù)界的圖類。顯然以f(x)=x為色數(shù)界的圖類就是完美圖。對任意給定圖H，如果圖G不含與H同構的圖為導出子圖，則稱圖G是H-free(不含H為導出子圖)的。Gyárfás給出猜想[6]：設F是一個森林，對于每一個F-free的圖G，存在整數(shù)函數(shù)f(F,ω(G))使得χ(G)≤f(F,ω(G))。

Wagon[7]證明了，Hoang[8]證明了。關于限制子圖的色數(shù)的更多結論可參閱文獻[9-11]。本文證明了不含2K2、C4和C5為導出子圖的圖是完美圖，進而證明了每一個不含2K2和C4為導出子圖的圖是(ω(G)+1)可著色的，并且給出一類滿足不含2K2和C4為導出子圖且χ(G)=ω(G)+1的圖類，這里2K2表示兩條獨立邊。

1 預備知識

設G=(V(G),E(G))表示一個圖，其中V(G)和E(G)分別表示圖G的頂點集和邊集。給定ν∈V(G)和A?V(G)，NG(ν)和G[A]分別表示圖G中ν的鄰點集和由A導出的子圖。文中涉及到的其他術語、符號參考文獻[1]。

設H為圖G的導出子圖，若H為長度至少為5的奇圈，則稱H為G奇洞；若H為長度至少為5的奇圈的補圖，則稱H為G的補奇洞。不含奇洞和補奇洞的圖稱為Berge圖。由Berge提出，Seymour等證明的強完美圖定理為：

定理1[4]圖G是完美圖當且僅當圖G是Berge圖。

圖G不含補奇洞即其補圖不含奇洞，所以圖G為Berge圖當且僅當G和都不含奇洞。所以強完美圖定理也可表示為：

定理2[4]圖G為完美圖示當且僅當G和都不含奇洞。

對于一些常見的完美圖有：

命題1[4]Split圖、二部圖及其補圖都是完美圖。

2 定理及其證明

定理3若圖G不含2K2，C4和C5為導出子圖，則圖G是完美圖，即χ(G)=ω(G)。

證明顯然，圖G不含長度大于等于6的圈為導出子圖，否則與G不含2K2為導出子圖矛盾。又由圖G不含C5為導出子圖，所以圖G不含奇洞。證明G的補圖也不含奇洞。假設含有C5為導出子圖，由于，所以G含有C5為導出子圖，矛盾。又若中含有長度大于5的奇洞，設為Cm(m≥7)，則取Cm中頂點都不相鄰的兩條邊ν1ν2，u1u2∈E(Cm),有，因而，即圖G中含有C4作為導出子圖，矛盾。由強完美圖定理2，圖G是完美圖。

定理3若圖G不含2K2和C4為導出子圖，則χ(G)≤ω(G)+1，且存在等號成立的圖。

證明若圖是不連通的，只需要考慮每個連通分支，故不失一般性，假設G是連通圖。設S為圖G的一個最大獨立集，則V(G)S中的每個點在S中至少有一個鄰點。令，，則A,B,S構成V(G)的一個劃分，且有如下結論。

結論1G(A)是完全圖。

假設存在x,y∈A，但xy?E(G)。由于x,y在 S中都僅有一個鄰點，分別設為。若，則是獨立集，與S是最大獨立集矛盾；若，則，矛盾。

結論2G[B]是完全圖。

假設存在x，y∈B，但xy?E(G)。若x,y在S中沒有公共的鄰點，即NG(x)∩NG(y)∩S=φ，設分別是x,y在S中各自的鄰點，則，矛盾；若x,y在S中僅有一個公共的鄰點，即NG(x)∩NG(y)∩S={u}，則x,y在S中還至少存在異于u的各自另外一個鄰點，設為,即，矛盾；若x,y在S中至少有2個公共的鄰點，即，設u,ν∈NG(x)∩NG(y)∩S，則G[x,y,u,ν]?C4，矛盾。

由結論1和結論2，可知G[A∪B]是二部圖的補圖，即為完美圖。而S是獨立集，所以χ(G)≤ω(G)+1。

構造滿足不含2K2和C4為導出子圖且χ(G)= ω(G)+1的圖G0。設x,y是完全圖Kn中的兩個點，ν1,ν2是路P3=ν1ν2ν3的兩個端點，，，，圖G0是由Kn和P3構成的階為n+3的圖，滿足V(G0)=V(Kn)∪V(P3)，E(G0)=E(Kn)∪E(P3)∪Eν1Eν2Eν3。顯然圖G0滿足不含2K2和C4為導出子圖，且ω(G0)=n?？紤]G0的色數(shù)χ(G0)，由G0的子圖Kn的著色擴充到G0的著色c，Kn至少需要n種顏色（每個頂點一種顏色），不妨設c(x)=1，c(y)=n,由于ν1與Kn中除了y外的所有頂點都相鄰，所以只能c(ν1)=n，否則χ(G0)=ω(G0)+1；同理由ν2與Kn中除了x,y外的所有頂點都相鄰，所以只能c(ν2)=1；由ν3與Kn中除了y外的所有頂點都相鄰，且ν2ν3∈E(G0)，所以ν3只能著1,2,…,n外的另外一種顏色，故χ(G0)=ω(G0)+1。

[1]Reinhard D.Graph theory(Second Edition)[M].Hong Kong：Springer-Verlag,2000：95-122.

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

[3]ReedB.ω,Δandχ[J].Journalofgraphtheory,1998,374：177-212.

[4]ChudnovskyM,RobertsonN,SeymourP.Thestrongperfect graphtheorem[J].AnnalsofMathematics,2006,164：51-229.

[5]宋春偉.強完美圖定理及相關問題[J].數(shù)學進展,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]張東翰.圖Dn,4的鄰點強可區(qū)別的全染色[J].商洛學院學報，2014,28(6)：8-9.

[10]Duan F,Wu B Y.On chromatic number of graphs without certaininducedsubgraphs[J].Arscombinatoria.2011(7)：33-4.

[11]段芳,張維娟.不含2K1+K2和C4作為導出子圖的圖的色數(shù)[J].華東師范大學學報：自然科學版,2014(1)：9-12.

（責任編輯：李堆淑）

Colouring for 2K2-free Graphs

WANG Xiao
（College of Mathematics and Computer Application,Shangluo University,Shangluo726000,Shaanxi）

By the strong perfect graph theorem,the result that every{2K2，C4，C5}-free graph is perfect graph was obtained.Moreover,the result that every{2K2，C4}-free graph is(ω(G)+1)-colourable was proved,a kind of graphs satisfying{2K2，C4}-free and χ(G)=ω(G)+1 was given,where χ(G)and ω(G)denote chromatic number and clique number respectively.

chromatic number;clique number;induced subgraph

O172

A

1674-0033（2015）02-0003-02

10.13440/j.slxy.1674-0033.2015.02.001

2014-12-18

商洛學院科研基金項目（09SKY005）

王曉，男，河南南陽人，碩士，講師