王曉

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

不含2K2為導(dǎo)出子圖的圖的染色

王曉

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

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

色數(shù)；團(tuán)數(shù)；導(dǎo)出子圖

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

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

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

設(shè)G=(V(G),E(G))表示一個(gè)圖，其中V(G)和E(G)分別表示圖G的頂點(diǎn)集和邊集。給定ν∈V(G)和A?V(G)，NG(ν)和G[A]分別表示圖G中ν的鄰點(diǎn)集和由A導(dǎo)出的子圖。文中涉及到的其他術(shù)語(yǔ)、符號(hào)參考文獻(xiàn)[1]。

設(shè)H為圖G的導(dǎo)出子圖，若H為長(zhǎng)度至少為5的奇圈，則稱(chēng)H為G奇洞；若H為長(zhǎng)度至少為5的奇圈的補(bǔ)圖，則稱(chēng)H為G的補(bǔ)奇洞。不含奇洞和補(bǔ)奇洞的圖稱(chēng)為Berge圖。由Berge提出，Seymour等證明的強(qiáng)完美圖定理為：

定理1[4]圖G是完美圖當(dāng)且僅當(dāng)圖G是Berge圖。

圖G不含補(bǔ)奇洞即其補(bǔ)圖不含奇洞，所以圖G為Berge圖當(dāng)且僅當(dāng)G和都不含奇洞。所以強(qiáng)完美圖定理也可表示為：

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

對(duì)于一些常見(jiàn)的完美圖有：

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

2 定理及其證明

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

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

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

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

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

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

結(jié)論2G[B]是完全圖。

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

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

構(gòu)造滿(mǎn)足不含2K2和C4為導(dǎo)出子圖且χ(G)= ω(G)+1的圖G0。設(shè)x,y是完全圖Kn中的兩個(gè)點(diǎn)，ν1,ν2是路P3=ν1ν2ν3的兩個(gè)端點(diǎn)，，，，圖G0是由Kn和P3構(gòu)成的階為n+3的圖，滿(mǎn)足V(G0)=V(Kn)∪V(P3)，E(G0)=E(Kn)∪E(P3)∪Eν1Eν2Eν3。顯然圖G0滿(mǎn)足不含2K2和C4為導(dǎo)出子圖，且ω(G0)=n?？紤]G0的色數(shù)χ(G0)，由G0的子圖Kn的著色擴(kuò)充到G0的著色c，Kn至少需要n種顏色（每個(gè)頂點(diǎn)一種顏色），不妨設(shè)c(x)=1，c(y)=n,由于ν1與Kn中除了y外的所有頂點(diǎn)都相鄰，所以只能c(ν1)=n，否則χ(G0)=ω(G0)+1；同理由ν2與Kn中除了x,y外的所有頂點(diǎn)都相鄰，所以只能c(ν2)=1；由ν3與Kn中除了y外的所有頂點(diǎn)都相鄰，且ν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]宋春偉.強(qiáng)完美圖定理及相關(guān)問(wè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]張東翰.圖Dn,4的鄰點(diǎn)強(qiáng)可區(qū)別的全染色[J].商洛學(xué)院學(xué)報(bào)，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作為導(dǎo)出子圖的圖的色數(shù)[J].華東師范大學(xué)學(xué)報(bào)：自然科學(xué)版,2014(1)：9-12.

（責(zé)任編輯：李堆淑）

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

商洛學(xué)院科研基金項(xiàng)目（09SKY005）

王曉，男，河南南陽(yáng)人，碩士，講師