不含相邻短圈平面图的全染色

Total Coloring of Planar Graphs Without Adjacent Short Cycles

摘要

基于权转移方法，研究一类平面图的全染色问题。结果表明，如果对于平面图G的每一个顶点v，都存在\left\{\mathrm{3,4},\mathrm{5,6},\mathrm{7}\right\}中的两个整数i_v和j_v，使得v不与相邻的i_v⁃圈和j_v⁃圈关联，则全染色猜想对图G成立。

Abstract

The problem on total coloring of one kind of planar graph is researched by using discharging method．The result shows that if for each vertex v of planar graph G，there are two integers i_v，j_v\in｛3，4，5，6，7｝， such that v is not incident with adjacent i_v ⁃cycles and j_v ⁃cycles，then total coloring conjecture holds for graph G．

关键词

平面图 / 全染色 / 圈 / 相邻

Key words

planar graph / total coloring / cycle / adjacent

图的染色理论起源于著名的四色问题，作为图论的重要内容，它在图与组合的研究当中占有重要的地位，同时在计算机理论、组合最优化、网络设计等方面也有广泛的应用。图的k⁃全染色是指用k种颜色对图的顶点和边同时进行染色，使得任意两个具有相邻关系或关联关系的元素染不同的颜色。如果一个图存在k⁃全染色，那么称这个图是k⁃全可染的。显然任何一个最大度为\mathrm{\Delta }的图都不是\mathrm{\Delta }⁃全可染的，即其全染色至少需要\left(\mathrm{\Delta }+\mathrm{1}\right)种颜色。20世纪60年代，Behzad^［1］和Vizing^［2］曾独立地提出著名的全染色猜想（简记为TCC）：每一个简单图都是\left(\mathrm{\Delta }+\mathrm{2}\right)⁃全可染的。

TCC已被广泛研究^［3⁃8］，文献［9⁃12］证明了当时TCC成立。对平面图来说，文献［13⁃15］分别证明了TCC对于\mathrm{\Delta }\ge \mathrm{9}、\mathrm{\Delta }=\mathrm{8}和\mathrm{\Delta }=\mathrm{7}的平面图成立。对于\mathrm{\Delta }=\mathrm{6}的平面图而言，孙向勇等^［16］证明了不含 l⁃圈时，TCC成立；陈明等^［17］证明了不含相交三角形时，TCC成立；朱恩强等^［18］证明了不含4⁃扇时，TCC成立；Roussel^［19］证明了如果对于图中每一个顶点v，都存在某个整数i_v\in \left\{\mathrm{3,4},\mathrm{5,6},\mathrm{7,8}\right\}，使得v不关联i_v⁃圈，那么TCC成立。本文拟研究不含相邻短圈平面图的全染色，得到TCC对于这类图也成立。

1 预备知识

本文所涉及的图都为有限简单无向图。不加定义的符号和术语可参见文献［20］。长度为k的圈称为 k⁃圈。3⁃圈又称为三角形。如果两个圈至少包含一条共同的边，则称这两个圈是相邻的。对于图的顶点v，用d\left(v\right)表示v的度数，即和v相关联的边的数目；若d\left(v\right)=k，则称v是一个k⁃点；若d\left(v\right)\ge k（或\le k），则称v是一个k^{+}⁃（或k^{-}⁃）点。设G是一个平面图，G的面的集合记为F，对于f\in F，用d\left(f\right)表示f的度数，即和f相关联的边的数目，并且每条割边要计算两次；类似于顶点，若d\left(f\right)=k、d\left(f\right)\ge k或d\left(f\right)\le k，则分别称f是一个k⁃面，k^{+}⁃面或k^{-}⁃面。若一个k⁃面f按顺时针方向的边界顶点依次为v_{\mathrm{1}},v_{\mathrm{2}},\cdots ,v_k，则将这个面记为f=v_{\mathrm{1}}{v}_{\mathrm{2}},\cdots ,v_k，并称这个面是一个\left(d(v_{\mathrm{1}}),d(v_{\mathrm{2}}),\cdots ,d(v_k)\right)⁃面。对于顶点v，用f_t(v)表示与v相关联的t⁃面个数。

2 主要结果及证明

2.1 主要结果

定理1　如果对于平面图G的每一个顶点v，都存在\left\{\mathrm{3,4},\mathrm{5,6},\mathrm{7}\right\}中的两个整数i_v和j_v，使得v不关联相邻的i_v⁃圈和j_v⁃圈，那么G是\left(\mathrm{\Delta }+\mathrm{2}\right)⁃全可染的。

需要指出两点：一是对于G中的顶点v来说，定理1中的i_v和j_v可能相等；二是对于G中两个不同的顶点u和v来说，定理1中的i_u（或j_u）与i_v（或j_v）也可能相等。因而，由定理1可推得文献［16］和［17］所得到的结论。

推论1^［16］　全染色猜想对不含l⁃圈的平面图成立（其中l\in \left\{\mathrm{3,4},\mathrm{5,6}\right\}）。

推论2^［17］　全染色猜想对不含相交三角形的平面图成立。

2.2 结构性质

由于文献［9⁃15］已证明\mathrm{\Delta }\ne \mathrm{6}的任意平面图都是\left(\mathrm{\Delta }+\mathrm{2}\right)⁃全可染的，因此欲证明定理1只需考虑\mathrm{\Delta }=\mathrm{6}的情形。假设定理1不真，设G=(V,E)是\mathrm{\Delta }=\mathrm{6}且满足定理1条件的\left|V\right|+\left|E\right|最小的反例，那么G的每一真子图都存在8⁃全染色，从而可以得到G具有如下的结构性质。

引理2^［21］　 G是2⁃连通的，G的每个面的边界都是圈。

引理3^［21］　设uv\in E，若d(u)\le \mathrm{3}，则d(u)+d(v)\ge \mathrm{9}。特别地，G没有2⁃点，并且3⁃点只能和6⁃点相邻。

引理4^［21］　 G不包含\left(\mathrm{3,6},\mathrm{6}\right)⁃三角形、\left(\mathrm{4,4},\mathrm{6}\right)⁃三角形和\left(\mathrm{4},{\mathrm{5}}^{-},{\mathrm{5}}^{-}\right)⁃三角形。

引理5^［22］　 G的4⁃面和5⁃面的边界上分别至多有一个3⁃点。

引理6^［22］　设v_{\mathrm{1}}{v}_{\mathrm{2}}{v}_{\mathrm{3}}是G的一个\left(\mathrm{4,5},\mathrm{6}\right)⁃三角形，其中d(v_{\mathrm{1}})=\mathrm{4}，d(v_{\mathrm{2}})=\mathrm{5}，d(v_{\mathrm{3}})=\mathrm{6}，则v_{\mathrm{1}}{v}_{\mathrm{2}}和v_{\mathrm{1}}{v}_{\mathrm{3}}都只关联一个三角形，即v_{\mathrm{1}}{v}_{\mathrm{2}}{v}_{\mathrm{3}}。

2.3 权转移

根据图G所具有的结构性质，应用权转移方法完成定理1的证明。

由握手定理\sum _{v\in V}d(v)=\mathrm{2}\left|E\right|=\sum _{f\in F}d(f)，可将连通平面图的欧拉公式\left|V\right|-\left|E\right|+\left|F\right|=\mathrm{2}改写成\sum _{v\in V}\left(\mathrm{2}d(v)-\mathrm{6}\right)+\sum _{f\in F}\left(d(f)-\mathrm{6}\right)=-\mathrm{12}。

首先给G的顶点v分配初始权ch(v)=\mathrm{2}d(v)-\mathrm{6}，给G的面f分配初始权ch(f)=d(f)-\mathrm{6}，则\sum _{x\in V\bigcup F}ch(x)=-\mathrm{12}。

以下将通过一个权转移规则，重新分配顶点和面的权。对于G的顶点v和面f，分别用c{h}^{\text{'}}(v)和c{h}^{\text{'}}(f)表示重新分配权后的权，因为权转移规则只是内部转移权，权转移过程保持权的总量不变，所以\sum _{x\in V\bigcup F}c{h}^{\text{'}}(x)=\sum _{x\in V\bigcup F}ch(x)=-\mathrm{12}。

证明对每个x\in V\bigcup F都有c{h}^{\text{'}}(x)\ge \mathrm{0}，从而可得\mathrm{0}\le \sum _{x\in V\bigcup F}c{h}^{\text{'}}(x)=\sum _{x\in V\bigcup F}ch(x)=-\mathrm{12}，即完成定理1所需的矛盾。

为方便起见，对于k⁃面f=v_{\mathrm{1}}{v}_{\mathrm{2}}\cdots v_k，用\left(d(v_{\mathrm{1}}),d(v_{\mathrm{2}}),\cdots ,d(v_k)\right)\to \left(c_{\mathrm{1}},c_{\mathrm{2}},\cdots ,c_k\right)表示点v_i向面f转移权c_i(i=\mathrm{1,2},\cdots ,k)。以下是所需要的权转移规则。

R1：转给3⁃面f=v_{\mathrm{1}}{v}_{\mathrm{2}}{v}_{\mathrm{3}}的权。

对于i\in \left\{\mathrm{1,2},\mathrm{3}\right\}，当d(v_i)=\mathrm{4}或5时，令

\alpha (v_i)=\raisebox{1ex}{$\left(ch(v_i)-\frac{\mathrm{1}}{\mathrm{2}}{f}_{\mathrm{4}}(v_i)-\frac{\mathrm{1}}{\mathrm{4}}{f}_{\mathrm{5}}(v_i)\right)$}\!\left/ \!\raisebox{-1ex}{$f_{\mathrm{3}}(v_i)$}\right.。

\left({\mathrm{5}}^{-},{\mathrm{5}}^{-},\mathrm{6}\right)\to \left(\alpha (v_{\mathrm{1}}),\alpha (v_{\mathrm{2}}),\mathrm{3}-\alpha (v_{\mathrm{1}})-\alpha (v_{\mathrm{2}})\right)；

\left({\mathrm{5}}^{-},\mathrm{6,6}\right)\to \left(\alpha (v_{\mathrm{1}}),\frac{\mathrm{3}-\alpha (v_{\mathrm{1}})}{\mathrm{2}},\frac{\mathrm{3}-\alpha (v_{\mathrm{1}})}{\mathrm{2}}\right)；

\left(\mathrm{5,5},\mathrm{5}\right)\to \left(\alpha (v_{\mathrm{1}}),\alpha (v_{\mathrm{2}}),\alpha (v_{\mathrm{3}})\right)；

\left(\mathrm{6,6},\mathrm{6}\right)\to \left(\mathrm{1,1},\mathrm{1}\right)。

R2：转给4⁃面f=v_{\mathrm{1}}{v}_{\mathrm{2}}{v}_{\mathrm{3}}{v}_{\mathrm{4}}的权。

\left({\mathrm{3}}^{-},\mathrm{6},{\mathrm{4}}^{+},\mathrm{6}\right)\to \left(\mathrm{0},\frac{\mathrm{3}}{\mathrm{4}},\frac{\mathrm{1}}{\mathrm{2}},\frac{\mathrm{3}}{\mathrm{4}}\right)；

\left({\mathrm{4}}^{+},{\mathrm{4}}^{+},{\mathrm{4}}^{+},{\mathrm{4}}^{+}\right)\to \left(\frac{\mathrm{1}}{\mathrm{2}},\frac{\mathrm{1}}{\mathrm{2}},\frac{\mathrm{1}}{\mathrm{2}},\frac{\mathrm{1}}{\mathrm{2}}\right)。

R3：转给5⁃面f=v_{\mathrm{1}}{v}_{\mathrm{2}}{v}_{\mathrm{3}}{v}_{\mathrm{4}}{v}_{\mathrm{5}}的权。

\left({\mathrm{3}}^{-},\mathrm{6},{\mathrm{4}}^{+},{\mathrm{4}}^{+},\mathrm{6}\right)\to \left(\mathrm{0},\frac{\mathrm{1}}{\mathrm{4}},\frac{\mathrm{1}}{\mathrm{4}},\frac{\mathrm{1}}{\mathrm{4}},\frac{\mathrm{1}}{\mathrm{4}}\right)；

\left({\mathrm{4}}^{+},{\mathrm{4}}^{+},{\mathrm{4}}^{+},{\mathrm{4}}^{+},{\mathrm{4}}^{+}\right)\to \left(\frac{\mathrm{1}}{\mathrm{5}},\frac{\mathrm{1}}{\mathrm{5}},\frac{\mathrm{1}}{\mathrm{5}},\frac{\mathrm{1}}{\mathrm{5}},\frac{\mathrm{1}}{\mathrm{5}}\right)。

R4：{\mathrm{8}}^{+}⁃面转给边界点的权。

{\mathrm{8}}^{+}⁃面向其边界上的每个顶点转移\frac{\mathrm{1}}{\mathrm{4}}。

由以上权转移规则知，每一个4⁃点至少向其关联的{\mathrm{3}}^{+}⁃面转移\frac{\mathrm{1}}{\mathrm{2}}，每一个5⁃点至少向其关联的3⁃面和{\mathrm{4}}^{+}⁃面分别转移\frac{\mathrm{4}}{\mathrm{5}}和\frac{\mathrm{1}}{\mathrm{2}}。下面证明对每个x\in V\bigcup F都有c{h}^{\text{'}}(x)\ge \mathrm{0}。

令f是G的一个面。如果d(f)\ge \mathrm{8}，那么由R4可知c{h}^{\text{'}}(f)\ge ch(f)-\frac{\mathrm{1}}{\mathrm{4}}\times d(f)=(d(f)-\mathrm{6})-\frac{\mathrm{1}}{\mathrm{4}}\times d(f)=\frac{\mathrm{3}}{\mathrm{4}}d(f)-\mathrm{6}\ge \mathrm{0}。如果\mathrm{6}\le d(f)\le \mathrm{7}，那么c{h}^{\text{'}}(f)=ch(f)=d(f)-\mathrm{6}\ge \mathrm{0}。如果d(f)=\mathrm{5}，由引理3、引理5和R3得c{h}^{\text{'}}(f)\ge ch(f)+\mathrm{m}\mathrm{i}\mathrm{n}\left\{\frac{\mathrm{1}}{\mathrm{4}}\times \mathrm{4},\frac{\mathrm{1}}{\mathrm{5}}\times \mathrm{5}\right\}=-\mathrm{1}+\mathrm{1}=\mathrm{0}。如果d(f)=\mathrm{4}，由引理3、引理5和R2得c{h}^{\text{'}}(f)\ge ch(f)+\mathrm{m}\mathrm{i}\mathrm{n}\left\{\frac{\mathrm{3}}{\mathrm{4}}\times \mathrm{2}+\frac{\mathrm{1}}{\mathrm{2}},\frac{\mathrm{1}}{\mathrm{2}}\times \mathrm{4}\right\}=-\mathrm{2}+\mathrm{2}=\mathrm{0}。

假设d(f)=\mathrm{3}，如果f不是(\mathrm{5,5},\mathrm{5})⁃三角形，由引理3、引理4和R1可得c{h}^{\text{'}}(f)\ge ch(f)+\mathrm{3}=-\mathrm{3}+\mathrm{3}=\mathrm{0}。现在设f=v_{\mathrm{1}}{v}_{\mathrm{2}}{v}_{\mathrm{3}}是一个(\mathrm{5,5},\mathrm{5})⁃三角形。如果对于任意i\in \left\{\mathrm{1,2},\mathrm{3}\right\}，都有f_{\mathrm{3}}(v_i)\le \mathrm{3}，那么v_i\left(i\in \left\{\mathrm{1,2},\mathrm{3}\right\}\right)至少向f转移\raisebox{1ex}{$\left(\mathrm{4}-\frac{\mathrm{1}}{\mathrm{2}}\times \mathrm{2}\right)$}\!\left/ \!\raisebox{-1ex}{$\mathrm{3}$}\right.=\mathrm{1}，从而c{h}^{\text{'}}(f)\ge ch(f)+\mathrm{1}\times \mathrm{3}=-\mathrm{3}+\mathrm{3}=\mathrm{0}。否则，不失一般性，假设f_{\mathrm{3}}(v_{\mathrm{1}})\ge \mathrm{4}，此时v_{\mathrm{1}}至少向f转移\frac{\mathrm{4}}{\mathrm{5}}，并且v_{\mathrm{1}}、v_{\mathrm{2}}、v_{\mathrm{3}}都关联着相邻的\mathrm{3,4},\mathrm{5,6}⁃圈。如果f_{\mathrm{3}}(v_{\mathrm{2}})\ge \mathrm{4}或f_{\mathrm{3}}(v_{\mathrm{3}})\ge \mathrm{4}，那么对于\left\{\mathrm{3,4},\mathrm{5,6},\mathrm{7}\right\}中的任意两个整数i和j，都有相邻的i⁃圈和j⁃圈关联着v_{\mathrm{2}}或v_{\mathrm{3}}，这与定理1的条件矛盾。因此f_{\mathrm{3}}(v_{\mathrm{2}})\le \mathrm{3}且f_{\mathrm{3}}(v_{\mathrm{3}})\le \mathrm{3}，进一步有，当f_{\mathrm{3}}(v_{\mathrm{2}})=f_{\mathrm{3}}(v_{\mathrm{3}})=\mathrm{3}时，有f_{{\mathrm{6}}^{+}}(v_{\mathrm{2}})=\mathrm{2}或f_{{\mathrm{6}}^{+}}(v_{\mathrm{3}})=\mathrm{2}，从而由R1可得c{h}^{\text{'}}(f)\ge ch\left(f\right)+(\frac{\mathrm{4}}{\mathrm{5}}+\mathrm{1}+\frac{\mathrm{4}}{\mathrm{3}})=-\mathrm{3}+\frac{\mathrm{47}}{\mathrm{15}}>\mathrm{0}。

因此对所有的面f都有c{h}^{\text{'}}(f)\ge \mathrm{0}。

令v是G的一个顶点。如果d(v)=\mathrm{3}，根据权转移规则，v没有转出权也没有转入权，所以c{h}^{\text{'}}(v)=ch(v)=\mathrm{2}\times \mathrm{3}-\mathrm{6}=\mathrm{0}。如果d(v)=\mathrm{4}或5，由R1、R2和R3知c{h}^{\text{'}}(v)\ge \mathrm{0}。下面考虑d(v)=\mathrm{6}的情形，可得到如下引理。

引理7 设f=vuw是G的一个3⁃面，其中d(v)=\mathrm{6}且\mathrm{4}\le d(u)\le \mathrm{5}\le d(w)，则v至多向f转移\frac{\mathrm{5}}{\mathrm{4}}。

证明 对d(u)和d(w)的取值进行讨论。

（1）设d(u)=\mathrm{4}且d(w)=\mathrm{6}。由权转移规则R1知u至少向f转移\frac{\mathrm{1}}{\mathrm{2}}，进而可得v至多向f转移\raisebox{1ex}{$\left(\mathrm{3}-\frac{\mathrm{1}}{\mathrm{2}}\right)$}\!\left/ \!\raisebox{-1ex}{$\mathrm{2}$}\right.=\frac{\mathrm{5}}{\mathrm{4}}。

（2）设d(u)=\mathrm{4}且d(w)=\mathrm{5}。令g是与uw关联且不同于f的那个面，g^{\text{'}}是与uv关联且不同于f的那个面。由引理6知g和g^{\text{'}}都是{\mathrm{4}}^{+}⁃面。

首先，假设f_{\mathrm{3}}(w)=\mathrm{4}。此时对于\left\{\mathrm{3,4},\mathrm{5,6}\right\}中的任意两个整数i和j，都有相邻的i⁃圈和j⁃圈关联着w。如果g是一个{\mathrm{6}}^{+}⁃面，由权转移规则R1知，w向f转移\frac{\mathrm{4}}{\mathrm{4}}=\mathrm{1}且u至少向f转移\raisebox{1ex}{$\left(\mathrm{2}-\frac{\mathrm{1}}{\mathrm{2}}\right)$}\!\left/ \!\raisebox{-1ex}{$\mathrm{2}$}\right.=\frac{\mathrm{3}}{\mathrm{4}}，那么v至多向f转移\mathrm{3}-\mathrm{1}-\frac{\mathrm{3}}{\mathrm{4}}=\frac{\mathrm{5}}{\mathrm{4}}。如果g是一个5⁃面，对于\left\{\mathrm{3,4},\mathrm{5,6},\mathrm{7}\right\}中的任意两个整数i和j，都有相邻的i⁃圈和j⁃圈关联着w，这与定理1的条件矛盾。如果g是一个4⁃面，由定理1的条件可得f_{{\mathrm{6}}^{+}}(u)\ge \mathrm{2}，那么u至少向f转移\mathrm{2}-\frac{\mathrm{1}}{\mathrm{2}}=\frac{\mathrm{3}}{\mathrm{2}}且w向f转移\raisebox{1ex}{$\left(\mathrm{4}-\frac{\mathrm{1}}{\mathrm{2}}\right)$}\!\left/ \!\raisebox{-1ex}{$\mathrm{4}$}\right.=\frac{\mathrm{7}}{\mathrm{8}}，从而v至多向f转移\mathrm{3}-\frac{\mathrm{3}}{\mathrm{2}}-\frac{\mathrm{7}}{\mathrm{8}}=\frac{\mathrm{5}}{\mathrm{8}}。

其次，假设f_{\mathrm{3}}(w)=\mathrm{3}。如果g是一个{\mathrm{6}}^{+}⁃面，那么u至少向f转移\frac{\mathrm{2}}{\mathrm{3}}且w至少向f转移\raisebox{1ex}{$\left(\mathrm{4}-\frac{\mathrm{1}}{\mathrm{2}}\right)$}\!\left/ \!\raisebox{-1ex}{$\mathrm{3}$}\right.=\frac{\mathrm{7}}{\mathrm{6}}，从而v至多向f转移\mathrm{3}-\frac{\mathrm{2}}{\mathrm{3}}-\frac{\mathrm{7}}{\mathrm{6}}=\frac{\mathrm{7}}{\mathrm{6}}。如果g是一个4⁃面或5⁃面，由定理1的条件可得f_{{\mathrm{6}}^{+}}(u)\ge \mathrm{1}，那么u至少向f转移\raisebox{1ex}{$\left(\mathrm{2}-\frac{\mathrm{1}}{\mathrm{2}}\right)$}\!\left/ \!\raisebox{-1ex}{$\mathrm{2}$}\right.=\frac{\mathrm{3}}{\mathrm{4}}且w向f转移\raisebox{1ex}{$\left(\mathrm{4}-\frac{\mathrm{1}}{\mathrm{2}}\times \mathrm{2}\right)$}\!\left/ \!\raisebox{-1ex}{$\mathrm{3}$}\right.=\mathrm{1}，从而v至多向f转移\mathrm{3}-\frac{\mathrm{3}}{\mathrm{4}}-\mathrm{1}=\frac{\mathrm{5}}{\mathrm{4}}。

最后，假设f_{\mathrm{3}}(w)\le \mathrm{2}。此时u至少向f转移\frac{\mathrm{1}}{\mathrm{2}}且w向f转移\raisebox{1ex}{$\left(\mathrm{4}-\frac{\mathrm{1}}{\mathrm{2}}\times \mathrm{3}\right)$}\!\left/ \!\raisebox{-1ex}{$\mathrm{2}$}\right.=\frac{\mathrm{5}}{\mathrm{4}}，从而v至多向f转移\mathrm{3}-\frac{\mathrm{1}}{\mathrm{2}}-\frac{\mathrm{5}}{\mathrm{4}}=\frac{\mathrm{5}}{\mathrm{4}}。

（3）设d(u)=\mathrm{5}且d(w)=\mathrm{5}。如果u和w都至多和三个3⁃面关联，那么u和w分别至少向f转移\raisebox{1ex}{$\left(\mathrm{4}-\frac{\mathrm{1}}{\mathrm{2}}\times \mathrm{2}\right)$}\!\left/ \!\raisebox{-1ex}{$\mathrm{3}$}\right.=\mathrm{1}，从而v至多向f转移\mathrm{3}-\mathrm{1}-\mathrm{1}=\mathrm{1}。如果u或w中有一个点至少关联四个3⁃面，那么由定理1的条件可得u和w中的另一个点至多关联三个3⁃面，所以u和w至少向f共转移\frac{\mathrm{4}}{\mathrm{5}}+\raisebox{1ex}{$\left(\mathrm{4}-\frac{\mathrm{1}}{\mathrm{2}}\times \mathrm{2}\right)$}\!\left/ \!\raisebox{-1ex}{$\mathrm{3}$}\right.=\frac{\mathrm{9}}{\mathrm{5}}，从而v至多向f转移\mathrm{3}-\frac{\mathrm{9}}{\mathrm{5}}=\frac{\mathrm{6}}{\mathrm{5}}。

（4）设d(u)=\mathrm{5}且d(w)=\mathrm{6}。此时u至少向f转移\frac{\mathrm{4}}{\mathrm{5}}，从而v至多向f转移\raisebox{1ex}{$\left(\mathrm{3}-\frac{\mathrm{4}}{\mathrm{5}}\right)$}\!\left/ \!\raisebox{-1ex}{$\mathrm{2}$}\right.=\frac{\mathrm{11}}{\mathrm{10}}。

检验6⁃点v的新权。由引理3、引理4和引理7可知6⁃点v至多向每个关联的它3⁃面转移\frac{\mathrm{5}}{\mathrm{4}}。

如果f_{\mathrm{3}}(v)\le \mathrm{3}，那么由R2和R3得c{h}^{{}^{\mathrm{\text{'}}}}(v)\ge ch(v)-f_{\mathrm{3}}(v)\times \frac{\mathrm{5}}{\mathrm{4}}-(\mathrm{6}-f_{\mathrm{3}}(v))\times \frac{\mathrm{3}}{\mathrm{4}}=\frac{\mathrm{3}}{\mathrm{2}}-\frac{\mathrm{1}}{\mathrm{2}}{f}_{\mathrm{3}}(v)\ge \mathrm{0}。如果f_{\mathrm{3}}(v)=\mathrm{4}，那么由定理1的条件可得f_{{\mathrm{6}}^{+}}(v)\ge \mathrm{1}或f_{{\mathrm{5}}^{+}}(v)=\mathrm{2}，所以c{h}^{{}^{\mathrm{\text{'}}}}(v)\gech(v)-\mathrm{4}\times \frac{\mathrm{5}}{\mathrm{4}}-\mathrm{m}\mathrm{a}\mathrm{x}\left\{\frac{\mathrm{3}}{\mathrm{4}},\right.\left.\frac{\mathrm{1}}{\mathrm{4}}\times \mathrm{2}\right\}>\mathrm{0}。如果f_{\mathrm{3}}(v)=\mathrm{5}，那么由定理1的条件可知v关联的唯一{\mathrm{4}}^{+}⁃面是一个{\mathrm{8}}^{+}⁃面，根据R4可得c{h}^{{}^{\mathrm{\text{'}}}}(v)\ge ch(v)-\mathrm{5}\times \frac{\mathrm{5}}{\mathrm{4}}+\frac{\mathrm{1}}{\mathrm{4}}=\mathrm{0}。如果f_{\mathrm{3}}(v)=\mathrm{6}，那么对于\left\{\mathrm{3,4},\mathrm{5,6},\mathrm{7}\right\}中的任意两个整数i和j，都有相邻的i⁃圈和j⁃圈关联着v，这与定理1的条件矛盾。

综上所述，对于每个x\in V\bigcup F都有c{h}^{\text{'}}(x)\ge \mathrm{0}，即完成了定理1的证明。

3 结论

本文利用最大度为6且8⁃全可染平面图的结构性质，借助权转移方法证明了全染色猜想对于不含相邻短圈的平面图成立，扩充了文献［16］和［17］所给出的图类，进一步推进了全染色猜想的研究。

参考文献

[1] BEHZAD M. Graphs and their chromatic numbers［D］. Michigan： Michigan State University， 1965.

[2] VIZING V G. Some unsolved problems in graph theory［J］. Russian Mathematical Surveys， 1968， 23（6）： 125-141.

[3] 王晓丽， 王慧娟， 刘彬. 最大度为7的平面图的全染色［J］. 山东大学学报（理学版）， 2017， 52（8） ：100-106.

[4] 谭香. 一类最大度为6的平面图的全染色［J］. 山东大学学报（理学版）， 2021， 56（11） ：71-75.

[5] 常建， 金珩. 最大度为7且短圈不正常相交的平面图的全染色［J］. 内蒙古师范大学学报（自然科学汉文版）， 2017， 46（1） ：1-5.

[6] ZHOU Y Y， ZHAO D Y， MA M Y， et al. Total coloring of recursive maximal planar graphs［J］. Theoretical Computer Science， 2022， 909： 12-18.

[7] LIANG Z S. Total coloring of claw⁃free planar graphs［J］. Discussiones Mathematicae Graph Theory， 2022， 42（3）： 771-777.

[8] WANG L T， WANG H J， WU W L. Minimum total coloring of planar graphs with maximum degree 8［J］. Journal of Combinatorial Optimization， 2023， 45（2）： 82.

[9] ROSENFELD M. On the total coloring of certain graphs［J］. Israel Journal of Mathematics， 1971， 9（3）： 396-402.

[10] VIJAYADITYA N. On total chromatic number of a graph［J］. Journal of the London Mathematical Society， 1971， S2-3（3）： 405-408.

[11] KOSTOCHKA A V. The total coloring of a multigraph with maximal degree 4［J］. Discrete Mathematics， 1977， 17（2）： 161-163.

[12] KOSTOCHKA A V. The total chromatic number of any multigraph with maximum degree five is at most seven［J］. Discrete Mathematics， 1996， 162（1-3）： 199-214.

[13] BORODIN O V. On the total coloring of planar graphs［J］. Journal Für Die Reine und Angewandte Mathematik， 1989， 394： 180-185.

[14] YAP H P. Total colourings of graphs， Lecture Notes in Mathematics ［M］. Berlin： Springer， 1996.

[15] SANDERS D P， ZHAO Y. On total 9⁃coloring planar graphs of maximum degree seven［J］. Journal of Graph Theory， 1999， 31（1）： 67-73.

[16] 孙向勇， 马巧灵. 不含l⁃圈平面图的全染色猜想［J］. 济南大学学报（自然科学版）， 2007， 21（4） ：306-310.

[17] 陈明， 王应前. 关于平面图全染色的一个注记［J］. 浙江师范大学学报（自然科学版）， 2007， 30（4） ：421-423.

[18] ZHU E Q， XU J. A sufficient condition for planar graphs with maximum degree 6 to be totally 8⁃colorable［J］. Discrete Applied Mathematics， 2017， 223： 148-153.

[19] ROUSSEL N. Local condition for planar graphs of maximum degree 6 to be total 8⁃colorable［J］. Taiwanese Journal of Mathematics， 2011， 15（1）： 87-99.

[20] BONDY J A， MURTY U S R. Graph theory with applications［M］. New York： American Elsevier Pub. Co.， 1976.

[21] 郭占海， 金珩， 常建. 最大度为6不含相邻弦6圈的平面图的全染色［J］. 内蒙古师范大学学报（自然科学汉文版）， 2018， 47（5） ：398-400.

[22] LEIDNER M. A larger family of planar graphs that satisfy the total coloring conjecture［J］. Graphs and Combinatorics， 2014， 30（2）： 377-388.

基金资助

内蒙古自治区高等学校科学技术研究资助项目“不含特殊子式图类的全染色与结构研究”(NJZY22599)

内蒙古自治区高等学校科学技术研究资助项目“扩容图的若干问题研究”(NJZY22600)

无穷维哈密顿系统及其算法应用教育部重点实验室开 放课题资助项目“基于哈密顿系统的非线性波研究”(2023KFZR02)