最大度为Δ的平面图的 (Δ+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-),女,黑龙江安达人,硕士研究生.研究方向:运筹学与控制论;图论.