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

盧秋麗， 王應前

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

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

盧秋麗， 王應前

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

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

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

0 引 言

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

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

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

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

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

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

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

1 定理1極小反例的性質

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

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

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

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

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

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

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

圖1 可約構型

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

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

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

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

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

假設φ(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.

假設φ(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]中都只出現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]中只出現2次.此時讓vw改染為7或8,uw改染為1,u改染為6,v改染為1,uv染5.引理6證畢.

設v為6-點，把圍繞著v的若干個相繼的面組成的一個構型叫作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 可能存在的叢

證明 根據叢的定義知d(v)=6,u,w,x,z是v的4個不同鄰點.若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)所示.

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

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

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

設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)所示.

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

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

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

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

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

2 定理1的證明

權轉移規則(如圖 3 所示)如下:

R1 給3-面f的權

由引理4～引理6知:3-面不關聯3-點;3-面至多關聯一個4-點;若3-面關聯一個4-點,則另外2個點至多有1個是5-點.

R1.3 若f是一個(5+,5+,5+)-面,則每個與f相關聯的5+-點轉權1給f.

R2 給4-面f的權

由引理3知,4-面至多關聯1個3-點.

R3 給5-面f的權

圖3 權的轉移規則

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

下面只需驗證G中3+-點的新權.

設v為3-點.由權轉移規則知,3-點既沒有轉出權也沒有接收權,因此,ch′(v)=ch(v)=0.

設v為6-點,用n表示與v相關聯的3-面的個數.注意到G中3-圈和6-圈不相鄰,則v至多關聯4個3-面,即n≤4.

當n=3時，由引理9和引理10知,此時v至少關聯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]上官敏樂,王應前,李喬.不含4-圈的平面圖的全色數[J].中國科學:A輯 數學,2006,36(12):1321-1326.

[11]耿建艷, 侯建鋒.最大度為6且不含5-圈或6-圈的平面圖可8-全染色[J].山東大學學報:理學版,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.

(責任編輯 陶立方)

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

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

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