最大度为6且不含5-圈和相邻4-圈的平面图是7-全可染的*

张静雯

(浙江师范大学 数理与信息工程学院,浙江 金华 321004)

最大度为6且不含5-圈和相邻4-圈的平面图是7-全可染的*

张静雯

(浙江师范大学 数理与信息工程学院,浙江 金华 321004)

运用Discharging方法,证明了最大度为6且不含5-圈和相邻4-圈的简单平面图是7-全可染的.所得结果改进了现有文献的相关结果.

平面图;全染色;最大度;5-圈;相邻4-圈

0 引 言

本文所研究的图是有限简单无向图,文中未加定义的术语和记号参阅文献[1].

如果图G可嵌入到平面上, 使得边仅在端点处相交,则称图G是可平面图;可平面图在平面内的一个嵌入叫平面图.对于平面图G,分别用V,E,F,Δ和δ表示平面图G的顶点集、边集、面集、最大度和最小度.k-圈是指长度为k的圈;两个圈相邻是指该两个圈至少有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.这方面的一些研究结果可参见文献[4-8].人们期望得到关于简单平面图全染色的最好结果,即证明平面图是(Δ+1)-全可染的.到目前为止,已经证明了在大多数情况下,简单平面图是(Δ+1)-全可染的.文献[9-11]分别证明了Δ≥11,Δ=10和Δ=9的平面图是(Δ+1)-全可染的;文献[12]证明了Δ≥7且不含4-圈的简单平面图是(Δ+1)-全可染的.本文研究的是关于Δ=6的平面图的全染色问题,得到如下结果:

定理1设G是Δ=6且不含5-圈和相邻4-圈的平面图,则图G是7-全可染的.

1 定理1的证明

假设定理1不成立,并设图G是定理1的一个使σ(G)=|V|+|E|最小的反例,即Δ(G)=6且不含5-圈和相邻4-圈,它本身不是7-全可染的,但它的每一个真子图都是7-全可染的,则图G有以下几个性质:

图1 可约构型

断言1[9]图G是2-连通的.

δ≥2,且因为图G是2-连通的,所以G的每个面的边界都是圈.

把度数为k的点叫做k-点;类似地,把度数至少为k的点叫做k+-点;把度数至多为k的点叫做k--点.(i,j)-边是指此边的2个端点的度数分别为i和j;(i,j,k)-面是指此3-面上的点的度数分别为i,j,k.

断言2[13]设xy∈E.若d(x)≤3,则d(x)+d(y)≥Δ+2=8.

特别地,G中2-点只与6-点相邻,3-点只与5+-点相邻.

断言3[13]图G中所有(2,6)-边的导出子图是一个森林.

断言4G不含图1所示的结构.其中标记为·的点在G中没有其他邻点.

假设G有如图1(b) 所示的子结构.由G的极小性可知,G′=G-u2u3是7-全可染的.假设φ是G′的一个7-全染色,抹去u2和u5的色,则得到图G的一个部分全染色,其中未染的元素是u2u3,u2和u5.

若7∈{φ(u4u5),φ(u5u6)},则当φ(u4u5)=7时,如果φ(u5u6)≠φ(u3u4),那么交换u3u4与u4u5的色,再将φ(u3u4)染给u2u3;如果φ(u5u6)=φ(u3u4),那么交换u1u2与u1u3的色,再将φ(u1u3)染给u3u5,φ(u3u5)染给u2u3;当φ(u5u6)=7时,则交换u1u2与u1u3的色,如果φ(u4u5)≠φ(u1u3),那么再将φ(u1u3)染给u3u5,φ(u3u5)染给u2u3;如果φ(u4u5)=φ(u1u3),那么交换u3u4与u4u5的色,再将φ(u3u4)染给u2u3;最后,重染u2和u5,又得G是7-全可染的,矛盾.

假设G有如图1(c)所示的子结构.由G的极小性可知,G′=G-u2u3是7-全可染的.假设φ是G′的一个7-全染色,抹去u2和u5的色,则得到图G的一个部分全染色,其中未染的元素是u2u3,u2和u5.

2 权转移

权转移规则如图2 所示.

图2 权转移规则

R1:转向2-点的权

与2-点相邻的2个6-点都向2-点转移权1.

R2:转向3-面的权

R2.2:若3-面不与3--点相关联,则3-面上的3个4+-点都向3-面转移权1.

R3:转向4-面的权

R3.1:若4-面与2个3--点相关联,则4-面上的2个5+-点都向4-面转移权1;

首先考察面的新权.

由图G不含5-圈知图G不含5-面,故无需验证5-面的新权.

设f为6+-面.由权转移规则知f既不转出权也不接受权,因此ch′(f)=ch(f)=d(f)-6≥0.

综上所述,对任意的面f∈F,ch′(f)≥0.

其次考察顶点的新权.

设v为2-点.由断言2和R1知,ch′(v)=ch(v)+1×2=-2+2=0.

设v为3-点.由权转移规则知v既不转出权也不接受权,即ch′(v)=ch(v)=0.

下面用t表示与v相关联的3-面的个数.

设v为6-点.

用n表示与v相邻的2-点个数,显然,n≤6.与6-点相邻的2-点分布情况如图3所示.以下分2种情形讨论:

图3 与6-点相邻的2-点分布情况(1≤n≤6)

最复杂的为t=0.用m表示与v相关联的4-面个数,由图G不含5-圈和相邻4-圈知m≤3.

注2由断言3和图G不含5-圈知,与v关联且关联的2个与v相邻的2-点的面是6+-面.

n=6.由注1和注2知,ch′(v)≥ch(v)-1×6=0.

n=5.由注2和图G不含相邻4-圈知v至少关联5个6+-面,且m≤1,从而根据注1,ch′(v)≥ch(v)-1×5-1=0.

n=4.由注2和图G不含相邻4-圈知m≤2,从而根据注1,ch′(v)≥ch(v)-1×4-1×2=0.

n=3.由注2和图G不含相邻4-圈知m≤3,从而根据注1,ch′(v)≥ch(v)-1×3-1×3=0.

n=2.由注2和图G不含相邻4-圈知m≤3,从而根据注1,ch′(v)≥ch(v)-1×2-1×3≥0.

n=1.由图G不含相邻4-圈知m≤3,从而根据注1,ch′(v)≥ch(v)-1-1×3≥0.

至此,对任意的x∈V∪F,ch′(x)≥0已得到验证.定理1得证.

[1]Bondy J A,Murty U S R.Graph theory with applications[M].London:Macmillan Press,1976.

[2]Vizing V G.Some unsolved problems in graph theory[J].Uspekhi Mat Nauk,1968,23(6):117-134.

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

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

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

[6]Rosenfeld M.On the total coloring of certain graphs[J].Israel J Math,1971,9(3):396-402.

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

[8]Yap H P.Total coloring of graphs[M].Belin:Spring-Verlag,1996.

[9] Borodin O V,Kostochka A V,Woodall D R.Total coloring of planar graphs with large maximum degree[J].Graph Theory,1997,26(1):53-59.

[10]Wang Weifan.Total chromatic number of planar graphs with maximum degree ten[J].Graph Theory,2007,54(1):91-102.

[11]Kowalik L,Sereni J S,krekovski R.Total coloring of plane graphs with maximum degree nine[J].SIAM Discrete Math,2008,22(4):1462-1479.

[12]Hou Jianfeng,Liu Guizhen,Cai Jiansheng.List edge and list total coloring of planar graphs without 4-cycles[J].Theoret Comput Sci,2006,369:250-255.

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

Onthe7-total-colorabilityofplanegraphswithmaximumdegree6without5-cyclesandadjacent4-cycles

ZHANG Jingwen

(CollegeofMathematics,PhysicsandInformationEngineering,ZhejiangNormalUniversity,JinhuaZhejiang321004,China)

By using the discharging method, it was proved that plane graphs with maximum degree 6 and without 5-cycles and adjacent 4-cycles were 7-totally-colorable. This improved the known results in literatures.

plane graph; total coloring; maximum degree; 5-cycles; adjacent 4-cycles

1001-5051(2011)03-0272-05

O157.5

A

*收文日期：2010-01-02；

2010-09-13

浙江省自然科学基金资助项目(Y6090699)

张静雯(1986-),女,陕西西安人,硕士研究生.研究方向:运筹学与控制论;图论.

(责任编辑 陶立方)