关于平面图的7-全可染性的一个注记*

陶 鑫， 王应前

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

本文的图指的是有限简单无向图，文中未加定义的术语和记号参阅文献［1］．

设G=(V，E)表示顶点集为V、边集为 E的图．若能用k种颜色对G进行染色，使得任意2个相邻或相关联的元素染有不同的色，则称G是k-全可染的．设F，Δ和δ分别表示平面图G的面集、最大度和最小度．显然，给每一个图进行全染色至少要用Δ+1个色．

猜想1［1］任何简单图G都是(Δ+2)-全可染的．

这一猜想被称为全染色猜想，简记为TCC．即使对于平面图，TCC在目前还没有得到完整证明．剩下未解决的情形是Δ=6［2-8］．有趣的是，对于简单平面图，大多数情况是(Δ+1)-全可染的［9-10］．

猜想2［11］若G是4≤Δ≤8的简单平面图，则G是(Δ+1)-全可染的．

对此，文献［12］证明了Δ≥7且不含有4-圈的平面图是(Δ+1)-全可染的;文献［11］证明了Δ=7且不含相邻三角形的平面图是8-全可染的．笔者则研究了Δ=6且不含5-圈和6-圈的平面图的全染色问题．

定理1 若G是Δ=6且不含5-圈和6-圈的平面图，则G是7-全可染的．

证明 假设定理1不成立，并设G是定理1的一个使σ(G)=|V|+|E|最小的反例，即G本身不是7-全可染的，但它的每一个真子图都是7-全可染的，则可得断言1．

断言1［9］G是2-连通的，从而δ≥2且G的每个面的边界都是圈．

把度为k的点叫做k-点．类似地，度不小于k的点叫做k+-点，度不大于k的点叫做k－-点．

断言2［12］设 xy∈E．若 d(x)≤3，则 d(x)+d(y)≥Δ +2=8．特别地，G 中2-点只与6-点相邻，3-点只与5+-点相邻．

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

图1 G不含有的构形

只证第5种情形(如图1(e)所示)，其他情形的证明可参阅文献［10-11，13］．假设G含有如图1(e)所示的构形．根据 σ(G)的极小性知，G'=G －uv是7-全可染的．令 φ:V(G')∪E(G')→{1，2，…，7}是G'的一个7-全染色．设对于x∈V，S(x)是与顶点x以及与x相关联的边染得的颜色集．如图1(e)所示，设 S(u)={1，2，…，6}，其中 φ(uq)=3，φ(uw)=4，φ(vm)=7，因此 φ(pq)=7．否则将 3 染给 uv，7 染给uq，这样得到G的一个7-全染色，矛盾．此时交换pq与pw的颜色，将3染给uv，7染给uq，这样得到了G的一个7-全染色，矛盾．因此，断言3成立．

以下将运用Discharging方法导出完成定理1证明所需要的矛盾．

首先，给G的顶点v分配初始权ch(v)=2d(v)－6，给G的面f分配初始权ch(f)=d(f)－6．由握

下面将定义一个权转移规则，重新分配点和面的权，并设ch'(x)是重新分配点和面的权后元素x∈于只是在同一个图的点和面之间进行权转移，权的总和应该保持不变，因此得到 －12≥0，即得到了证明定理1所需要的矛盾．

权转移规则如下(如图2所示):

R1:转向2-点的权

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

R2:转向3-面的权

由断言2知，3-面上只有1个3－-点，因此

R2．1:若3-面含有3－-点，则此3-面上的2 个5+-点都向此

R2．2:若3-面不含3－-点，则此3-面上的3 个4+-点都向此3-面转移权 1．

R3:转向4-面的权

R3．1:若4-面含有2个3－-点，则此4-面上的2个5+-点都向此4-面转移权1;

R3．2:若4-面含有1个3－-点，则此4-面上与此3－-点相对的那个4+-点向此

R3．3:若4-面不含3－-点，则此4-面上的4 个4+-点都向此4-面

图2 权转移规则

首先考察面的新权．

设 f为3-面．若 f有1 个3－-点，则根据R2．2，ch'(f)=ch(f)+1 ×3=0．

设 f为4-面．若 f含有2 个3－-点，则根据 R3．1，ch'(f)=ch(f)+1 ×2=0;若f含1 个3－-点，则根据

由G不含5-圈和6-圈知G不含5-面和6-面，故无需验证5-面和6-面的新权．

设f为7+-面．由权转移规则知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为4-点．由 G 不含5-圈和6-圈知 t≤2，且 v至少与2 个7+-面关联．根据 R2．2 和 R2．3，v至多转移权1给每个相关联的3-面，至多转移

设v为5-点．由G不含5-圈和6-圈知t≤3，且v至少与2个7+-面关联．又由断言3(如图1(a)所示)知v至多与2个含有3－-点的3-面关联，根据R2和R3

设v为6-点．用n表示与v相邻的2-点个数，显然，n≤6．与6-点相邻的2-点分布情况如图3所示．下面根据n的大小来讨论v的新权:

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

n=6．由断言3(如图1(d)所示)知，v不与3-面关联．由G不含5-圈和6-圈以及断言3(如图1(e)所示)知，与v关联且关联2个与v相邻的2-点的面是7+-面．因此，v关联6个7+-面，根据R1，

n=5．由断言3(如图1(d)所示)知t=0．由G不含5-圈和6-圈知，v至少关联5个7+-面，根据R1和R3，

n=4．如图3(a1)、图 3(a2)、图 3(a3)所示，由断言3(如图1(d)所示)知 t≤1．若 t=1，则由 G 不则v至少关联 4个7+-面，根据R1和R3，ch'(v)≥ch(v)－1×4－1×2－0×4=0．

n=3．如图3(b1)、图3(b2)、图3(b3)所示，由断言3(如图1(d)所示)知 t≤2．若1≤t≤2，则由 G不含5-圈和6-圈知v至少关联4个7+-面，根据R1，R2和R3，

若 t=0，则 v至少关联3个7+-面，根据 R1和 R3，ch'(v)≥ch(v)－1×3－0×3－1×3=0．

n=2．如图3(c1)、图3(c2)、图3(c3)所示，由断言 3(如图1(d)所示)知 t≤2．若1≤t≤2，则由 G不含5-圈和6-圈知v至少关联3个7+-面，根据R1，R2．1和R3，

若t=0，则v至少关联2个7+-面，根据R1和R3，ch'(v)≥ch(v)－1×2－0×2－1×4=0．

设含有2-点的3-面是特殊3-面，记作s-面．由断言3(如图1(b)和图1(c)所示)知，若6-点与一个s-面关联，则6-点不与其他含有3－-点的3-面关联．

n=1．若v与s-面关联，则由 G不含5-圈和6-圈知 t≤4，且 v至少关联2个7+-面，根据 R1，R2和

若v不与s-面关联，则 t≤3．若t=3，则根据G不含5-圈和6-圈，v要关联3个7+-面，从而

若0≤t≤2，则v至少关联2个7+-面，从而

n=0．由G不含5-圈和6-圈知t≤4，且v至少关联2个7+-面，根据R1，R2和R3，

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

［1］Bondy J A，Murty U S R．Graph theory［M］．Berlin:Springer，2008．

［2］Rosenfeld M．On the total coloring of certain graphs［J］．Israel J Math，1971，9(3):396-402．

［3］Kostochka A V．The total coloring of a multigraph with maximal degree 4［J］．Discrete Math，1977，17(2):161-163．

［4］Kostochka A V．The total chromatic number of any multigraph with maximal degree five is at most seven［J］．Discrete Math，1996，162(2):199-214．

［5］Borodin O V．On the total coloring of planar graphs［J］．J Reine Angew Math，1989，394(2):180-185．

［6］陈明，王应前．关于平面图全染色的一个注记［J］．浙江师范大学学报:自然科学版，2007，30(4):421-423．

［7］Sanders D P，Zhao Yue．On total 9-coloring planar graphs of maximum degree seven［J］．J Graph Theory，1999，319(1):67-73．

［8］Wang Yingqian，Shangguan Minle，Li Qiao．On total chromatic number of planar graphs without 4-cycles［J］．Sci China Ser A，2007，50(1):81-86．

［9］Borodin O V，Kostochka A V，Woodall D R．Total coloring of planar graphs with large maximum degree［J］．J Graph Theory，1997，26(1):53-59．

［10］Wang Weifan．Total chromatic number of planar graphs with maximum degree ten［J］．J Graph Theory，2007，54(1):91-102．

［11］Du Dingzhu，Shen Lan，Wang Yingqian．Planar graphs with maximum degree 8 and without adjacent triangles are 9-totally-colorable［J］．Discrete Appl Math，2009，157(1):2778-2784．

［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(4):250-255．

［13］Kowalik L，Sereni J S，Skrekovski R．Total coloring of plane graphs with maximum degree nine［J］．SIAM J Discrete Math，2008，22(4):1462-1479．