不含4-和5-圈的平面圖的均勻染色*

王維凡, 桂 浩

(浙江師范大學(xué) 數(shù)理與信息工程學(xué)院,浙江 金華 321004)

0 引 言

本文所指的圖均為有限的、無向的簡(jiǎn)單圖.給定一個(gè)圖G,分別用V(G),E(G),|G|,δ(G),Δ(G)(簡(jiǎn)記為Δ)表示G的頂點(diǎn)集合、邊集合、階、最小度和最大度.一個(gè)圖G的頂點(diǎn)k-染色是指V(G)到顏色集合{1,2,…,k}的一個(gè)映射φ,使得任意2個(gè)相鄰的頂點(diǎn)x和y滿足φ(x)≠φ(y);G的色數(shù)χ(G)定義為使得G有k-染色的最小整數(shù)k;給定G的一個(gè)k-染色φ,用Vi表示染顏色i的頂點(diǎn)集合;如果對(duì)任一對(duì)i, j∈{1,2,…,k}有||Vi|-|Vj||≤1,那么就稱φ為G的均勻染色,或者G是均勻k-可染的;圖G的均勻色數(shù)定義為: χe(G)=min{k | G是均勻k-可染的}.

顯然, χe(G)≥χ(G),且不等式可以嚴(yán)格成立.1973年,Meyer[1]引進(jìn)了圖的均勻染色的概念,并提出以下猜想:

猜想1若G不是完全圖也不是奇圈,則χe(G)≤Δ.

1970年,Hajnal等[2]證明了對(duì)于k≥Δ+1,任意一個(gè)最大度為Δ的圖G都是均勻k-可染的;文獻(xiàn)[3]應(yīng)用算法分析給出了一個(gè)新的且短的證明;1994年,文獻(xiàn)[4]提出以下猜想：

猜想2[4]如果一個(gè)連通圖G不是Km,C2m+1和K2m+1,2m+1(m≥1),那么圖G是均勻Δ-可染的.

文獻(xiàn)[4]證明了猜想2對(duì)Δ≤3的圖成立;文獻(xiàn)[5]證明了猜想2對(duì)Δ=4的圖也成立.此外,猜想2還被證明對(duì)下面特殊圖類成立:樹[6]、 二部圖[7]、外平面圖[8]及Δ≥14d+1的d-退化圖[9]等.這里,如果G的每一個(gè)導(dǎo)出子圖H包含一個(gè)度至多為d的頂點(diǎn),那么就稱圖G為d-退化的.文獻(xiàn)[10]證明了猜想2對(duì)于Δ≥13的平面圖是成立的;文獻(xiàn)[11]將這個(gè)結(jié)果改進(jìn)到Δ≥9的情形.因此,對(duì)于平面圖族,僅剩下5≤Δ≤8的情形沒有解決.文獻(xiàn)[12]證明了:Δ≥7且沒有4-,5-圈的平面圖滿足猜想2;文獻(xiàn)[13]證明了圍長(zhǎng)大于或者等于5的平面圖滿足猜想2.

本文旨在改進(jìn)文獻(xiàn)[12]中的結(jié)果,將證明:每一個(gè)5≤Δ≤6且沒有4-,5-圈的平面圖滿足猜想2.本文的結(jié)果和文獻(xiàn)[4-5,12]中的結(jié)果隱含著猜想2對(duì)所有沒有4-,5-圈的平面圖成立.

1 結(jié)構(gòu)引理

在給出2個(gè)結(jié)構(gòu)引理之前,需要引進(jìn)一些記號(hào)和術(shù)語.設(shè)G是一個(gè)嵌入在平面上的圖;用F(G)表示G的面集合;對(duì)x∈V(G)∪F(G),用d(x)表示v在G中的度;一個(gè)度為k(至少k)的點(diǎn)(或面)被稱為k-點(diǎn)(或面)和k+-點(diǎn)(或面);用NG(v)表示一個(gè)頂點(diǎn)v在G中鄰點(diǎn)的集合;對(duì)i≥1,用ni(v)表示與v相鄰的i-點(diǎn)的個(gè)數(shù),ni(G)表示G中i-點(diǎn)的個(gè)數(shù).此外,用mk(v)表示與v關(guān)聯(lián)的k-面的個(gè)數(shù),k≥3.G的一個(gè)以u(píng)1,u2,u3為邊界點(diǎn)的3-面記作[u1u2u3].特別地,當(dāng)d(ui)=ai(i=1,2,3)時(shí),記此面為(a1,a2,a3)-面.

引理1若G是一個(gè)Δ=6,|G|≥5且沒有4-和5-圈的連通的平面圖,則G包含圖1中的子圖形之一.

證明 反證法.假設(shè)G不含H1～H12中的任何一個(gè).因?yàn)镚是連通的且|G|≥5,所以δ(G)≥1.將圖G嵌入到平面上,則有以下斷言：

斷言11)n1(G)≤2.如果n1(G)=2,那么n2(G)=0.

圖1 引理1中的子圖形H1～H12

下面將設(shè)計(jì)一個(gè)恰當(dāng)?shù)臋?quán)轉(zhuǎn)移規(guī)則,按照此規(guī)則重新分配點(diǎn)和面的權(quán),從而得到一個(gè)新的權(quán)函數(shù)w′.而權(quán)轉(zhuǎn)移前后所有點(diǎn)和面的權(quán)的總和是保持不變的.

注1在圖1和下面的圖2中,實(shí)心點(diǎn)的度數(shù)與圖中顯示的度數(shù)相同,空心點(diǎn)可以同圖中以外的點(diǎn)相連.在每一個(gè)子圖形中,所有標(biāo)有xi的點(diǎn)都是不重合的.

設(shè)v是一個(gè)d(v)≥4的頂點(diǎn).權(quán)轉(zhuǎn)移規(guī)則定義如下:

R0:v給每一個(gè)相鄰的好2-點(diǎn)轉(zhuǎn)權(quán)1.

R1:若d(v)=4,則v平分剩余的權(quán)2-n2(v)給相關(guān)聯(lián)的3-面.

因?yàn)镚不含4-圈和5-圈,且G不含4-,5-面和相鄰3-面,所以下面斷言成立:

設(shè)w′表示在執(zhí)行規(guī)則R0～R3之后的結(jié)果權(quán)函數(shù).對(duì)任何x∈V(G)∪F(G),計(jì)算w′(x)的值.

首先,設(shè) f∈F(G),那么d(f)≥3.由上面分析知,d(f)≠4和5.若d(f)≥6,則w′(f)=w(f)=d(f)-6≥0.假設(shè)d(f)=3,且設(shè)f=[xyz]滿足d(x)≤d(y)≤d(z),那么d(x)≥2,d(z)≤6.

若d(x)≥5,則由規(guī)則R2和R3知,w′(f)≥-3+351=0.

1)n1(G)=2.

2)n1(G)≤1.

由斷言1的2),并注意到Ⅱ-壞點(diǎn)是成對(duì)出現(xiàn)的,可分下面幾種子情形:

由斷言1中的3),并注意到Ⅰ-壞點(diǎn)也是成對(duì)出現(xiàn)的,進(jìn)一步有下面子情形:

綜上，總可推出下面矛盾:

圖2 引理2中的子圖形 H13

引理1證畢.

類似地,可以證明下面引理：

引理2若G是一個(gè)Δ=5,|G|≥5且沒有4-和5-圈的連通的平面圖,則G包含H1,H3～H12和如圖2所示的子圖形H13.

2 主要結(jié)果

引理3[14]沒有5-圈的平面圖是3-退化的.

引理4[2]對(duì)k≥Δ+1,任意最大度為Δ的圖G是均勻k-可染的.

引理5設(shè)G=G1∪G2滿足V(G1)∩V(G2)=?.若G1和G2是均勻k-可染的,則G也是均勻k-可染的.

引理6[12]設(shè)S={v1,v2,…,vk}是G的頂點(diǎn)子集,且v1,v2,…,vk互不相同.若G-S是均勻k-可染的,且對(duì)每一個(gè)1≤i≤k有|NG(vi)-S|≤k-i,則G也是均勻k-可染的.

定理1若G是一個(gè)Δ=5,且沒有4-和5-圈的平面圖,則對(duì)任意的k≥5,G是均勻k-可染的.

證明 由引理4知,只需證明G是均勻5-可染的.對(duì)G的階進(jìn)行歸納證明.若|G|≤5,則結(jié)論顯然成立.假設(shè)|G|≥6.若G中的每個(gè)連通分支都至多只有4個(gè)頂點(diǎn),則Δ≤3.由引理4和引理5知,G是均勻5-可染的.否則,G有一個(gè)連通分支的階至少為5.由引理2知,G包含子圖形H1,H3～H12,H13之一(如圖1和圖2所示).令k=5,選取子集合S如下:

若G包含Hi,i∈{3,4,6,7,8,10,11,12,13},則令S={x1,x2,x3,x4,x5}.

若G包含Hi,i∈{1,5,9},則令S={x1,x2,x3,x4,x5}.其中,x2為G-{x1,x3,x4,x5}中一個(gè)度至多為3的頂點(diǎn).由引理3知,x2一定存在.

容易驗(yàn)證上面定義的S滿足:對(duì)每一個(gè)1≤i≤k,有|NG(vi)-S|≤k-i.設(shè)H=G-S,則H是一個(gè)沒有4-圈和5-圈的平面圖,Δ(H)≤Δ=5.若Δ(H)≤4,則由引理4知,H是均勻5-可染的.若Δ(H)=5,則由引理5和歸納假設(shè)知,H也是均勻5-可染的.總之,H有一個(gè)均勻5-染色.由引理6知,G是均勻5-可染的.定理1證畢.

定理2若G是一個(gè)Δ=6,且沒有4-和5-圈的平面圖,則對(duì)任意的k≥6,G是均勻k-可染的.

證明 由引理4知,只需證明G是均勻6-可染的.對(duì)G的階進(jìn)行歸納證明.若|G|≤6,則結(jié)論顯然成立.假設(shè)|G|≥7.若G中的每個(gè)連通分支都至多只有5個(gè)頂點(diǎn),則Δ≤4.由引理4和引理5知,G是均勻6-可染的.否則,G有一個(gè)連通分支的階至少為6.由引理1知,G包含子圖形H1～H12之一,如圖1所示.令k=6,由引理6知,只需選取子集合S如下:

若G包含H2,則令S={x1,x2,…,x6}.

若G包含Hi,i∈{3,4,6,7,8,10,12},則令S={x1,x2,…,x6}.其中,x3為G-{x1,x2,x4,x5,x6}中一個(gè)度至多為3的頂點(diǎn);

若G包含H11,則令S={x1,x2,…,x6}.其中,x2為G-{x1,x3,x4,x5,x6}中一個(gè)度至多為3的頂點(diǎn).

若G包含Hi,i∈{1,5,9},則令S={x1,x2,…,x6}.其中,x2是G-{x1,x4,x5,x6}中度至多為3的頂點(diǎn),x3是G-{x1,x2,x4,x5,x6}中度至多為3的頂點(diǎn).由引理3知,x2,x3存在.定理2證畢.

定理1、定理2和文獻(xiàn)[4-5,12]中的結(jié)果蘊(yùn)含著下面定理:

定理3每一個(gè)沒有4-和5-圈的平面圖是均勻Δ-可染的.

參考文獻(xiàn)：

[1]Meyer W.Equitable coloring[J].Amer Math Monthly,1973,80(8):920-922.

[2]Hajnal A,Szemeréi E.Proof of a conjecture of Erd?s[J].Combinatorial Theory and Its Applications,1970,2:601-623.

[3]Kierstead A,Kostochka A,Mydlarz M,et al.A fast algorithm for equitable coloring[J].Combinatorica,2010,30(2):217-224.

[4]Chen B L,Lih K W,Wu Poulin.Equitable coloring and the maximum degree[J].European J Combin,1994,15(5):443-447.

[5]Kierstead A,Kostochka A.Every 4-colorable graph with maximum degree 4 has an equitable 4-coloring[J].J Graph Theory,2012,71(1):31-48.

[6]Chen B L,Lih K W.Equitable coloring of trees[J].J Combin Theory Ser B,1994,61(1):83-87.

[7]Lih K W,Wu Poulin.On equitable coloring of bipartite graphs[J].Discrete Math,1996,151(1/2/3):155-160.

[8]Kostochka A V.Equitable colorings of outerplanar graphs[J].Discrete Math,2002,258(1/2/3):373-377.

[9]Kostochka A V,Nakprasit K,Pemmaraju S V.Equitable colorings ofk-degenerate graphs[J].Combin Probab Comput,2006,19(1):53-60.

[10]Zhang Yi,Yap H P.Equitable colorings of planar graphs[J].J Combin Math Combin Comput,1998,27(1):97-105.

[11]Nakprasit K.Equitable colorings of planar graphs with maximum degree at least nine[J].Discret Math,2012,312(5):1019-1024.

[12]Zhu Junlei,Bu Yuehua.Equitable list colorings of planar graphs without short cycles[J].Theoret Comput Sci,2008,407(1/2/3):21-28.

[13]Nakprasit K,Nakprasit K.Equitable colorings of planar graphs without short cycles[J].Theoret Comput Sci,2012,465:21-27.

[14]Wang Weifan,Lih K W.Choosability and edge choosability of planar graphs without five cycles[J].Appl Math Lett,2002,15(5):561-565.