盧秋麗， 王應(yīng)前

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

最大度為Δ的平面圖的 (Δ+2)-全可染性*

盧秋麗， 王應(yīng)前

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

研究了Δ=6的平面圖的(Δ+2)-全可染性,證明了Δ=6且3-圈和6-圈不相鄰的平面圖是8-全可染的.這一結(jié)果進(jìn)一步擴(kuò)展了(Δ+2)-全可染(平面圖)圖類.

平面圖;全染色;最大度;圈

0 引 言

本文所研究的圖是有限簡單無向圖,文中未加定義的術(shù)語和記號參閱文獻(xiàn)[1].

若圖G可嵌入到平面內(nèi),使得邊僅在端點(diǎn)處相交,則稱圖G是可平面圖;可平面圖在平面內(nèi)的一個嵌入叫平面圖.對于平面圖G,用V,E,F,Δ和δ分別表示它的頂點(diǎn)集、邊集、面集、最大度和最小度.長度為k的圈簡稱為k-圈.若2個圈至少有1條公共邊,則稱它們相鄰.

對于圖G=(V,E),若存在映射φ:V∪E→{1,2,…,k},使得對任意相鄰或相關(guān)聯(lián)的元素x,y∈V∪E都有φ(x)≠φ(y),則稱G是k-全可染的.顯然,給每一個圖進(jìn)行全染色至少要用Δ+1種顏色.文獻(xiàn)[2-3]猜想:任何簡單圖G都是(Δ+2)-全可染的.這一猜想就是著名的全染色猜想(Total Coloring Conjecture),簡記為TCC.

即使對于平面圖,TCC也未得到完整的證明.唯一未解決的困難情形是Δ=6.對于Δ≤5 的任意圖已被證明TCC是正確的[4-6];文獻(xiàn)[7]解決了Δ≥9的平面圖的情況;文獻(xiàn)[8]證明了Δ=8的平面圖是10-全可染的;文獻(xiàn)[9]證明了Δ=7的平面圖是9-全可染的.關(guān)于Δ=6的平面圖的(Δ+2)-全可染性,文獻(xiàn)[10]證明了Δ=6且不含4-圈的平面圖是8-全可染的;文獻(xiàn)[11]證明了最大度為6且不含5-圈或6-圈的平面圖是8-全可染的;文獻(xiàn)[12]證明了不含帶弦的4-圈或帶弦的5-圈或帶弦的6-圈的平面圖是8-全可染的.本文進(jìn)一步研究Δ=6的平面圖的8-全可染性,證明了以下定理:

定理1若G是3-圈和6-圈不相鄰的平面圖,則G是(Δ+2)-全可染的.

推論1若G沒有k-圈,k∈{3,6},則G是(Δ+2)-全可染的.

設(shè)v是圖G的一個頂點(diǎn)，稱與v相關(guān)聯(lián)的邊的條數(shù)為v在G中的度數(shù),記作d(v);設(shè)f是平面圖G的一個面，稱f的邊界的長度為f的度數(shù),記作d(f);把度數(shù)為k的點(diǎn)(面)叫作k-點(diǎn)(面);把度數(shù)至少(多)為k的點(diǎn)(面)叫作k+(k-)-點(diǎn)(面);兩端點(diǎn)的度數(shù)分別為i和j的邊叫作(i,j)-邊;稱點(diǎn)v的一個i-鄰點(diǎn)是一個與v相鄰且度數(shù)為i的點(diǎn);與點(diǎn)v相鄰的點(diǎn)所形成的集合記作N(v).若f的所有邊界點(diǎn)按某個時針方向依次為v1,v2,…,vk,則稱f是一個(d(v1),d(v2),…,d(vk))-面.

1 定理1極小反例的性質(zhì)

注意到文獻(xiàn)[4-9]已證明Δ≠6的平面圖是(Δ+2)-全可染的,故只證明Δ=6且3-圈和6-圈不相鄰的平面圖G是8-全可染的,就可以完成定理1的證明.

假設(shè)定理1不成立,設(shè)圖G是定理1的一個使σ(G)=|V|+|E|最小的反例，Δ=6.由G的選取知,G本身不是8-全可染的,但它的每一個真子圖都是8-全可染的.以下是圖G的若干結(jié)構(gòu)性質(zhì):

引理1[3]G是2-連通的,從而圖G中每個面的邊界都是圈.

引理2[12]設(shè)xy∈E.若d(x)≤3,則d(x)+d(y)≥Δ+3=9.

推論2圖G無2-點(diǎn),從而δ≥3且G中的3-點(diǎn)只與6-點(diǎn)相鄰.

引理3圖G不含(3,6,3,6)-面.

證明 假設(shè)f是G中的一個(3,6,3,6)-面.刪去f上所有的(3,6)-邊得到圖G′,由極小性可知,G′是8-全可染的.抹去所有與f相關(guān)聯(lián)的3-點(diǎn)的顏色,則得到G的一個局部全染色,其中只有與f相關(guān)聯(lián)的邊和3-點(diǎn)未染色.因為每條未染的邊的可用色至少為2,且偶圈是2-邊可選的,所以所有未染的邊可補(bǔ)染好,最后再將3-點(diǎn)補(bǔ)染好,就可得到圖G的一個8-全染色,矛盾.引理3證畢.

圖1 可約構(gòu)型

引理4[11]圖G中不含(3,6,6)-面.

引理5[12]圖G中不含(4,4,6)-面.

引理6圖G中不含(4,5,5)-面.

1)φ(u)∈{6,7,8},不妨設(shè)φ(u)=8.斷言S[u]={1,2,…,8},否則讓u改染為不在S[u]中的色,uv染8,從而G是9-全可染的,矛盾.因此,S[u]={1,2,…,8},且每個色在S[u]中都只出現(xiàn)1次.為了討論方便，設(shè)φ(uw)=α,S(u){φ(uv),φ(uw)}={β,γ}.

2)φ(u){6,7,8},即{α,β,γ}={6,7,8},φ(u)∈{1,2,3,4},不妨設(shè)α=6,β=7,γ=8.

假設(shè)φ(u)∈{2, 3, 4}.斷言7,8∈{a,b,c,φ(w)},否則若 7{a,b,c,φ(w)},則讓vw改染為7,uv染1.同理,8∈{a,b,c,φ(w)}.斷言5∈{a,b,c,φ(w)},否則讓uw改染為5,uv染6.則此時{2,3,4}{φ(u)}中至少有1個色可染給uw,然后讓uv染6.

假設(shè)φ(u)=1.斷言{a,b,c,φ(w)}={2,3,4,5},否則若2{a,b,c,φ(w)},則讓uw改染為2,uv染6.同理,3,4,5∈{a,b,c,φ(w)}.斷言S[u]={1,2,…,8},否則讓u改染為不在S[u]中的色,vw改染為7或8,uv染1.因此,S[u]={1,2,…,8}且每個色在S[u]中都只出現(xiàn)1次.斷言{6,7,8}?{φ(N(v))},否則若6{φ(N(v))},則讓v改染為6,uv染5.同理,7,8∈{φ(N(v))}.因為φ(w)∈{2,3,4,5},則1在S[v]中只出現(xiàn)2次.此時讓vw改染為7或8,uw改染為1,u改染為6,v改染為1,uv染5.引理6證畢.

設(shè)v為6-點(diǎn)，把圍繞著v的若干個相繼的面組成的一個構(gòu)型叫作v處的一個叢.若按某個時針方向，叢的面度序列為(k1,k2,…,kl),則稱這個叢是一個(k1,k2,…,kl)-叢.

引理7若3-面f1=[uvw]和5-面f2=[vwxyz]形成v處的一個(3,5)-叢,則u=y,從而d(u)=d(y)≥4.如圖2(a)所示.

證明 若u{x,y,z},則3-圈uvwu與6-圈vuwxyzv相鄰,矛盾.因此,u∈{x,y,z}.若u=x,則d(w)=2,這與δ≥3矛盾.同理,u≠z.因此,u=y.引理7證畢.

引理8若3-面f1=[uvw],3-面f2=[wvx]和4-面f3=[vxyz]形成v處的一個(3,3,4)-叢,則u=y,從而d(u)=d(y)≥4.如圖2(b)所示.

圖2 可能存在的叢

證明 根據(jù)叢的定義知d(v)=6,u,w,x,z是v的4個不同鄰點(diǎn).若u≠y,則3-圈uvwu與6-圈vuwxyzv相鄰,矛盾.故u=y.引理8證畢.

引理9若3-面f1=[uvw],4+-面f2和3-面f3=[vxy]形成v處的一個(3,4+,3)-叢,則f2是7+-面.如圖2(c)所示.

證明 根據(jù)叢的定義知d(v)=6,u,w,x,y是v的4個不同鄰點(diǎn).

設(shè)f2=[vwpx]是一個4-面.因為δ≥3,所以p≠u,p≠y.此時,3-圈uvwu與6-圈vuwpxyv相鄰,矛盾.

設(shè)f2=[vwpqx]是一個5-面.由引理7知u=q,此時,C=vqxv是一個3-圈分離了點(diǎn)y和p,即y≠q,從而3-圈vxyv與6-圈vyxqpwv相鄰,矛盾.

設(shè)f2=[vwpmqx]是一個6-面,則3-圈uvwu和6-圈vwpmqxv相鄰,矛盾.

綜上，f2是7+-面.引理9證畢.

引理10若4+-面f1,3-面f2=[uvw],3-面f3=[vwx],3-面f4=[vxy]和4+-面f5形成v處的一個(4+,3,3,3,4+)-叢,則f1和f5至少有一個是7+-面.如圖2(d)所示.

證明 根據(jù)叢的定義知d(v)=6,p,u,w,x,y,z是v的6個不同鄰點(diǎn).

設(shè)f1=[vpqmnu]是一個6-面,則3-圈uvwu和6-圈vpqmnuv相鄰,矛盾.同理,f5也不是6-面.

設(shè)f1=[vpqmu]是一個5-面,則由引理7知q=w,此時C=vpwv是一個3-圈分離了點(diǎn)m與x,y,即m≠x且m≠y，從而3-圈vxyv與6-圈vumwxyv相鄰,矛盾.因此,f1不是5-面.同理,f5也不是5-面.

設(shè)f1=[vpqu]和f5=[vymz]都是4-面,則由引理8知,q=x,m=w.又因為3-圈vpxv分離了點(diǎn)m和w,即m≠w,所以可得到矛盾.

綜上，f1和f5至少有一個是7+-面.引理10證畢.

2 定理1的證明

權(quán)轉(zhuǎn)移規(guī)則(如圖 3 所示)如下:

R1 給3-面f的權(quán)

由引理4～引理6知:3-面不關(guān)聯(lián)3-點(diǎn);3-面至多關(guān)聯(lián)一個4-點(diǎn);若3-面關(guān)聯(lián)一個4-點(diǎn),則另外2個點(diǎn)至多有1個是5-點(diǎn).

R1.3 若f是一個(5+,5+,5+)-面,則每個與f相關(guān)聯(lián)的5+-點(diǎn)轉(zhuǎn)權(quán)1給f.

R2 給4-面f的權(quán)

由引理3知,4-面至多關(guān)聯(lián)1個3-點(diǎn).

R3 給5-面f的權(quán)

圖3 權(quán)的轉(zhuǎn)移規(guī)則

由以上權(quán)轉(zhuǎn)移規(guī)則可知,對G中的每個面f均有ch′(f)≥0.

下面只需驗證G中3+-點(diǎn)的新權(quán).

設(shè)v為3-點(diǎn).由權(quán)轉(zhuǎn)移規(guī)則知,3-點(diǎn)既沒有轉(zhuǎn)出權(quán)也沒有接收權(quán),因此,ch′(v)=ch(v)=0.

設(shè)v為6-點(diǎn),用n表示與v相關(guān)聯(lián)的3-面的個數(shù).注意到G中3-圈和6-圈不相鄰,則v至多關(guān)聯(lián)4個3-面,即n≤4.

當(dāng)n=3時，由引理9和引理10知,此時v至少關(guān)聯(lián)1個7+-面.由注1,R2和R3知,

至此,對任意的x∈V∪F,ch′(x)≥0已得到驗證.定理1證畢.

[1]Bondy J A,Murty U S R.Graph theory[M].Berlin:Springer,2008.

[2]Behzad M.Graphs and their chromatic numbers[D].Michigan:Michigan State University,1965.

[3]Vizing V G.Some unsolved problems in graph theory[J].Russ Math Surv,1968,23(6):125-141.

[4]Vijayaditya N.On total chromatic number of a graph[J].J London Math Soc,1971,3(2):405-408.

[5]Kostochka A V.The total coloring of a multigraph with maximal degree 4[J].Discrete Math,1977,17(2):161-163.

[6]Kostochka A V.The total chromatic number of any multigraph with maximum degree five is at most seven[J].Discrete Math,1996,162(1/2/3):199-214.

[7]Borodin O V.On the total coloring of planar graphs[J].J Reine Angew Math,1989,394:180-185.

[8]Andersen L.Total coloring of simple graph[D].Aalborg:University of Aalborg,1993.

[9]Sanders D P,Zhao Yue.On total 9-coloring of planar graphs of maximum degree seven[J].J Graph Theory,1999,31(1):67-73.

[10]上官敏樂,王應(yīng)前,李喬.不含4-圈的平面圖的全色數(shù)[J].中國科學(xué):A輯 數(shù)學(xué),2006,36(12):1321-1326.

[11]耿建艷, 侯建鋒.最大度為6且不含5-圈或6-圈的平面圖可8-全染色[J].山東大學(xué)學(xué)報:理學(xué)版,2006,41(5):55-58.

[12]Hou Jianfeng,Liu Guizhen，Xin Yongxun,et al.Some results on total colorings of planar graphs[J].J Appl Math,2008,26(3/4):511-517.

(責(zé)任編輯 陶立方)

Onthe(Δ+2)-totalcolorabilityofplanegraphswithmaximumdegreeΔ

LU Qiuli, WANG Yingqian

(CollegeofMathematics,PhysicsandInformationEngineering,ZhejiangNormalUniversity,JinhuaZhejiang321004,China)

It was studied 8-total colorability of plane graphs with maximum degree 6. It was showed that plane graphs with maximum degree 6 without adjacent 3-cycles and 6-cycles were 8-totally-colorable. The result extended the graph class of (Δ+2)-totally-colorable.

plane graphs; total coloring; maximum degree; cycles

O157.5

A

1001-5051(2013)01-0054-06

2012-09-14

浙江省自然科學(xué)基金資助項目(Y6090699)

盧秋麗(1985-),女,黑龍江安達(dá)人,碩士研究生.研究方向:運(yùn)籌學(xué)與控制論;圖論.