关于最大度为7的平面图全染色的一个注记＊

王应前， 孙 强， 陶 鑫

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

0 引言

本文未加定义的术语和记号请参阅文献［1］．除特别说明外，本文所研究的图都是有限简单无向图．用V，E，F，Δ和δ分别表示平面图G的顶点集、边集、面集、最大度和最小度．若V∪E中的元素能用k个颜色进行染色，使得任意2个相邻或相关联的元素染有不同的色，则称G是k-全可染的．显然，给每个图进行全染色至少要用Δ+1个色．Vizing猜想:任何简单图G都是(Δ+2)-全可染的．这一猜想被称为全染色猜想，简记为TCC．

虽然已有大量的文献［2-8］对TCC进行了深入的研究，但是即使对于平面图，TCC也仍未得到完整的证明，唯一未解决的困难情形是Δ=6．对于简单平面图，大多数情况下是(Δ+1)-全可染的．文献［9-11］相继证明了Δ≥11，Δ=10，Δ=9的平面图是(Δ+1)-全可染的．对于Δ≤8的平面图，要得到如文献［9-11］那样简洁的结果似乎非常困难．本文研究了Δ=7的平面图的全可染性，得到如下结果:

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

1 结构

假设定理1不成立，设G是定理1的一个使σ(G)=|V|+|E|最小的反例，即G本身不是8-全可染的，但它的每个真子图都是8-全可染的，则G有以下几个性质:

引理1 G是2-连通的，从而δ≥2且G的每个面的边界都是圈．

称度为k的点为k-点．类似地，称度不小于k的点为k+-点，度不大于k的点为k--点．

引理2 设xy∈E．若d(x)≤3，则d(x)+d(y)≥Δ+2=9．特别地，G中2-点只与7-点相邻，3-点只与6+-点相邻．

引理1和引理2的证明可参见文献［9］．

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

图1 G中不存在的结构

设f∈F，f的周界(即按某个方向绕f一周的闭途径)的长度记为d(f)，称其为面f的度．称d(f)=k的面为k-面．类似地可定义k+-面和k--面．若一个k-面沿着某个方向的点依次为v1，v2，…，vk，则称这个面为一个(d(v1)，d(v2)，…，d(vk))-面．

下面将给出引理3(d)的证明，其余证明可参阅文献［12-13］．

引理4 G不含图2所示的结构，其中标记为·的点在G中没有其他邻点．

图2 G中不存在的结构

情形 1 |{φ(e8)，φ(e9)，φ(e10)，φ(e11)}|≥2．由于 E，F，H 都是 5-点，此时先依次染好 e1，e3，e6，染的颜色分别记为 α，β，γ;再将{c(E)，c(H)，c(F)}{α，β，γ}中的色染给{e2，e4，e5，e7}中的若干条边;然后再染好{e2，e4，e5，e7}中剩下的边，此时O的禁用色恰好为7个，故顶点O可染;最后再染好M，N，L，P，从而得到G的一个8-全染色，矛盾．

情形2 |{φ(e8)，φ(e9)，φ(e10)，φ(e11)}|=1．设 φ(e8)=φ(e9)=φ(e10)=φ(e11)=ζ，若 ζ∉{φ(E)，φ(F)，φ(H)}，此时先依次染好 e1，e3，e6;再按照情形1的染色方案得到 G的一个8-全染色，矛盾．故设 ζ∈{φ(E)，φ(F)，φ(H)}，令 ζ=φ(E)．当|S［E］|≤7 时，改染顶点 E 的颜色为 θ，让 e1染φ(E)，再依次染好e3，e6，此时可按照情形1的染色方案易得G的一个8-全染色，矛盾;当|S［E］|=8时，EA和EB中至多只有1条边(不妨设为EA)与E的邻点染有相同的颜色，交换EB与e8的颜色，将顶点E的颜色改染为φ(EB)，此时先依次染好e1，e3，e6，然后按照情形1的染色方案易得G的一个8-全染色，矛盾．同理可证当ζ=φ(F)或φ(H)时，易得G的一个8-全染色，矛盾．说明G中不含如图2(a)所示的结构．

2)假设G中存在如图2(b)所示的结构，由σ(G)的极小性知，G'=G-O是8-全可染的．令φ:V(G')∪E(G')→{1，2，…，8}是 G'的一个8-全染色．抹去 M，N，L，C 的颜色．

情形 1 |{φ(e8)，φ(e9)，φ(e10)}|≥2．由于 A，B，D 都是 5-点，此时先依次染好 e7，e2，e4，e5，染的颜色分别记为 α，β，γ，η;再将{c(A)，c(B)，c(D)}{α，β，γ，η}中的色染给{e1，e3，e6}中的若干条边;然后再染好{e1，e3，e6}中剩下的边，此时O的禁用色恰好为7个，故O可染;最后再染好M，N，L，C，从而得到G的一个8-全染色，矛盾．

情形2 |{φ(e8)，φ(e9)，φ(e10)}|=1．设 φ(e8)=φ(e9)=φ(e10)=φ(e11)=ζ．若 ζ∉{φ(A)，φ(B)，φ(D)}，此时先依次染好e7，e2，e4，e5;再按照情形1的染色方案得到G 的一个8-全染色，矛盾．故设 ζ∈{φ(A)，φ(B)，φ(D)}，令 ζ=φ(A)．当 |S［A］|≤7 时，改染顶点 A 的颜色为 θ，让 e2染 φ(A)，再依次染好e7，e4，e5，此时可按照情形1的染色方案易得G的一个8-全染色，矛盾;当|S［A］|=8时，EA和HA中至多只有1条边(不妨设为EA)与A的邻点染有相同的颜色，交换HA与e10的颜色，将顶点A的颜色改染为φ(HA)，同样可按照情形1的染色方案易得G的一个8-全染色，矛盾．同理可证，若ζ=φ(B)，则易得G的一个8-全染色，矛盾．

若ζ=φ(D)且 φ(CI)=φ(D)，则当 |S［D］|≤7时，改染顶点D的颜色为 θ，让e4染 φ(D)，按照情形1的染色方案易得G的一个8-全染色，矛盾;当|S［D］|=8时，DH和DI中至多只有1条边与D的邻点染有相同的颜色，若DI与D的邻点染有相同的颜色，则交换DH与e10的颜色，并将顶点D的颜色改染为φ(DH)，此时可按照情形1的染色方案易得G的一个8-全染色，矛盾，若DH与D的邻点染有相同的颜色，则交换CI和DI的颜色，接着交换CF和e9的颜色，将顶点D的颜色改染为φ(DI)，可按照情形1的染色方案易得G的一个8全染色，矛盾．

若ζ=φ(D)且φ(CI)≠φ(D)，则交换CF和e9的颜色，此时可按照情形1的染色方案易得G的一个8-全染色，矛盾．说明G中不含图2(b)所示的结构．引理4证毕．

2 权转移

以下将运用Discharging方法导出完成定理1证明所需要的矛盾．首先，给G的顶点v分配初始权-12．

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

R1:给2-点v的权．

由引理3知，v只与7-点相邻．每个与v相邻的7-点转权1给v．

R2:给3-面 f的权．

由引理2和引理3知，3-面上至多只有1个4--点．

图3 权转移规则

注1 6+-点不转权给与其相关联的6+-面;6+-点至多转与其相关联的4-面;进一步，5-点至多转

由以上权转移规则可知，对G中的每个面f均有ch'(f)≥0成立，且对所有的2-点v，ch'(v)≥0也成立．下面只需验证G中3+-点的新权．

设v为3-点．由上面的权转移规则可知，3-点既没转出权也不接收权，故ch'(v)=ch(v)=0．下面用t表示与v相关联的3-面个数．

设v为7-点．设n为与7-点v相邻的2-点个数，则n≤7．

为方便起见，先引入几个记号:τ(v→)表示从v转出的权和;t表示与v相关联的3-面的个数．一些依次围绕顶点v的面形成一个v扇，简称为扇．称一个扇是极大的，如果扇的始边和终边都是(7，2)边(即连接7-点和2-点的边)，而扇中与v相关联的其他边均不是(7，2)边．通常把一个由k个面组成的扇

注2 设面f与v相关联，且v至少与1个不在f上的2-点相邻．若f与2个2-点相关联，同时这2个2-点与v相邻，则由引理3知f是一个6+-面;若f只与1个2-点相关联，同时这个2-点与v相邻，则由引理3知f是一个4+-面．

当2≤n≤5时，n个2-点在7-点v周围的分布情况如图4所示．

图4 当2≤n≤5时，n个2-点在v周围的分布情况

综上即能证得定理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］Yap H P．Total coloring of graphs［M］．Belin:Spring-Verlag，1996．

［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］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．

［12］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(13):2778-2784．

［13］Shen Lan，Wang Yingqian，Wang Weifan，et al．On the 9 total colorability of planar graphs with maximum degree 8 andwithout intersecting triangles［J］．Applied Mathematics Letters，2009，22(9):1369-1373．