最大度大于等于八的可嵌入图的全染色

Total Coloring of Embedded Graphs with Maximum Degree at Least Eight

摘要: 图的染色问题是图论中的一个重要研究方向，在计算机科学，组合优化和网络优化等方面有非常重要的应用，全然色是一种重要的染色。本文利用权值转移的方法证明了，如果G是最大度大于等于八的可嵌入到欧拉示性数非负曲面的图，且G中不包含相邻的4-圈，那么图G的全色数等于最大度加一。

Abstract: Graph coloring is an important research direction in graph theory. It has very important applica-tions in computer science, combination optimization and network optimization. Total coloring is an important type of coloring. In this paper, we use the discharging method to prove that if G is a graph of maximum degree that is equal or greater than eight, and it can be embedded into a nonnegative surface of Euler characteristic, and G does not contain adjacent 4-cycles, then the total chromatic number of G is equal to its maximum degree plus one.

1. 引言

本文仅考虑可嵌入到欧拉示性数非负的曲面的图，且这些图是无向的、有限的，简单的且非空的图。文中未加定义直接使用的概念和符号可以参考文献 [1]。分别用 $V\left(G\right)$， $F\left(G\right)$， $E\left(G\right)$ 表示图的点集，面集和边集。设 $v\in V\left(G\right)$，则v的度数 $d\left(v\right)$ 是与v相关联的边的个数。 $\Delta \left(G\right)$ 代表图G的最大度，即 $\Delta \left(G\right)=\max \left\{d\left(v\right),v\in V\left(G\right)\right\}$，简写为 $\Delta$。同样的，图G的面f的度数 $d\left(f\right)$ 是面的边界所含边的个数。如果图G中存在连接顶点u和v的路，则称这两个顶点是连通的。若图G的任意两个顶点是连通的，则称图G是连通图。如果存在V的子集 $V^{\prime }$，使得 $G-V^{\prime }$ 不连通，则称是 $V^{\prime }$ 是G的顶点割。k-顶点割是包含k个元素的顶点割，G中所有具有k顶点割中最小的k，称为G的连通度，记作 $\kappa (G)$。如果 $\kappa \left(G\right)\ge k$，则称G是k-连通的。一个图G的k-全染色，是指从集合 $V\left(G\right)\cup E\left(G\right)$ 到集合 $\left\{1,2,\cdots ,k\right\}$ 的一个映射，使得在集合 $V\left(G\right)\cup E\left(G\right)$ 的任意两个相邻或相关联的元素的值不相等。如果可以用k种颜色对图G全染色，那么则称图G是k-可全染色的，使得图G是k-可全染色的最小正整数k称为图G的全色数 ${\chi }^{″}\left(G\right)$。

猜想1 对于任意的简单图G都有， $\Delta \left(G\right)+1\le {\chi }^{″}\left(G\right)\le \Delta \left(G\right)+2$。

这个猜想称为全染色(TCC)猜想，在20世纪60年代，由Vizing [2] 和Behzad [3] 分别独立提出。全染色猜想在 $\Delta \left(G\right)\le 5$ 时，对于一般图成立，而对于平面图，当 $\Delta \left(G\right)=6$ 时，尚未完全证明 [4]，本文中考虑的图G是可以嵌入到欧拉示性数非负的曲面上的图，即 $\chi \left(\Sigma \right)\ge 0$。对于可以嵌入到欧拉示性数 $\chi \left(\Sigma \right)\ge 0$ 的曲面上的图，Zhao Y.证明了当 $\Delta \left(G\right)\ge \text{8}$ 时，全染色猜想成立 [5]，Wang H. J.和Liu B.将结果推广到 $\Delta \left(G\right)\ge 7$ [6]。Wang Y.对可嵌入到欧拉示性数非负曲面的图的全染色进行完善 [7]。随着研究的深入，人们发现一些图的全色数不仅仅满足全染色猜想，还有更强的结论，即 ${\chi }^{″}\left(G\right)=\Delta \left(G\right)+1$。Wang B.和Wu J. L.证明了当 $\Delta \left(G\right)\ge \text{7}$，且不含相邻3-圈和4-圈时 ${\chi }^{″}\left(G\right)\le \Delta \left(G\right)+1$ [8]。

Figure 1. Forbidden structure of subgraph.

图1. 禁用子图结构

2. 引理

引理1 [9] G是2-连通的。

引理2 [10] 如果 $uv\in E\left(G\right)$ 且 $d(u)\le 4,$ 那么 $d\left(u\right)+d\left(v\right)\le \Delta +2=10$。

引理3 [11] 图G中连接2-点与8-点的边导出的子图是森林。

引理4 [12] 图G中不包含同构于如图1的禁用子图结构。(图中实心点表示已经画出与其关联的所有边，空心点表示没有画出与其关联的所有边。图中 $d\left(v\right)=7$。)

3. 主要结果的证明

基于以上引理，下面开始证明我们的主要结论。

定理1 设G是 $\Delta \left(G\right)\ge 8$ 可嵌入到欧拉示性数非负曲面的图，且G中不包含相邻的4-圈，那么图G的全色数 ${\chi }^{″}\left(G\right)\text{=}\Delta \left(G\right)+1$。

为方便证明下面给出一些定义和符号。在图G中，令k-点，k⁻-点，k⁺-点分别表示在图G中度数等于k的点，度数小于等于k的点，度数大于等于k的点。类似的，我们可以定义k-面，k⁻-面，k⁺-面。令 $n_k\left(v\right)$ 代表与v相邻的k-点的个数，类似的可以定义， $n_k^{-}\left(v\right)$， $n_k^{+}\left(v\right)$。令 $f_k\left(v\right)$ 代表与v相关联的k-面的个数，类似的可以定义， $f_k^{-}\left(v\right)$， $f_k^{+}\left(v\right)$。

由于图G是可以嵌入到欧拉示性数非负曲面上的图，所以由Euler公式 $\left|V\right|+\left|E\right|-\left|F\right|=\chi \left(\Sigma \right)\ge 0$ 得，

$-6\left(\left|V\right|+\left|E\right|-\left|F\right|\right)={\displaystyle \underset{v\in V\left(G\right)}{\sum }\left(2d\left(v\right)-6\right)+{\displaystyle \underset{f\in F\left(G\right)}{\sum }\left(d\left(f\right)-6\right)=}}-6\chi \left(\Sigma \right)\le 0$

假设图G是满足定理条件的一个极小反例。首先定义初始权值，对于任意的 $v\in V\left(G\right)$，设初始权值为 $ch\left(v\right)=2d\left(v\right)-6$，对于任意的 $f\in F\left(G\right)$，设初始权值为 $ch\left(f\right)=d\left(f\right)-6$。然后对于任意的 $x\in V(G)\cup F(G)$ 按照权转移规则对权值重新分配得到新的权值 $c{h}^{\prime }\left(x\right)$，由于权转移规则只是移动权值，而不会改变权值的总和，所以转移后的权值总和小于等于0。即

${\displaystyle \underset{x\in V(G)\cup F(G)}{\sum }c{h}^{\prime }\left(x\right)={\displaystyle \underset{x\in V(G)\cup F(G)}{\sum }ch\left(x\right)}}\le 0$

需要验证，对权值进行重新分配后，对于任意的 $x\in V\left(G\right)\cup F\left(G\right)$，都有 $c{h}^{\prime }\left(x\right)\ge 0$，并且当 $d\left(v\right)\ge 8$，有 $c{h}^{\prime }\left(x\right)>0$，由于在文献 [13] 中， $d\left(v\right)\ge 9$ 已经证明过此结论，所以只需要证明当 $d\left(v\right)=8$ 时，有 $c{h}^{\prime }\left(x\right)>0$，那么得出转移后的权值总和严格大于0，得出矛盾，所以不存在这样的反例，即定理成立。

接下来给出如下的权值转移规则。要注意的是，权转移是在相邻的点之间，或者相关联的面之间进行转移。

R1 2-点从两个邻点各得1。

R2 4-点给3-面或4-面 $\frac{\text{1}}{\text{2}}$，给5-面 $\frac{\text{1}}{\text{3}}$。

R3 5-点给3-面1，给4-面 $\frac{\text{1}}{\text{2}}$，给5-面 $\frac{\text{1}}{\text{3}}$。

R4 6-点给3-面 $\frac{\text{5}}{\text{4}}$，给4-面 $\frac{\text{3}}{\text{4}}$，给5-面 $\frac{\text{1}}{\text{3}}$。

R5 7⁺-点给与3⁻点关联的3-面 $\frac{\text{1}}{\text{3}}$，给不与3⁻点关联的3-面1，给与两个3⁻-点关联的4-面1，给其余的4-面 $\frac{\text{3}}{\text{4}}$，给5-面 $\frac{\text{1}}{\text{3}}$。

现在开始验证，对于任意的 $f\in F\left(G\right)$，设 $d\left(f\right)\ge 6$，则 $c{h}^{\prime }\left(f\right)=ch\left(f\right)-6\ge 0$。设 $d\left(f\right)=5$，则f至多与两个3⁻-点相邻，即f至少与三个4⁺-点相邻。所以 $c{h}^{\prime }\left(f\right)\ge ch\left(f\right)-6+\frac{1}{3}\times 3=0$。设 $d\left(f\right)=4$，当f与两个3⁻-点关联，则f与两个7⁺-点关联，所以 $c{h}^{\prime }\left(f\right)\ge ch\left(f\right)-6+1\times 2=0$。当f与一个3⁻-点，两5⁻-点相关联，f与两个7⁺-点相关联，所以 $c{h}^{\prime }\left(f\right)\ge ch\left(f\right)-6+\frac{3}{4}\times 2+\frac{1}{2}=0$。当f不与一个3⁻-点相关联，则 $c{h}^{\prime }\left(f\right)\ge ch\left(f\right)-6+\frac{1}{2}\times 4=0$。设 $d\left(f\right)=3$，当f与3⁻-点关联，则f与两个7⁺-点相关联，所以 $c{h}^{\prime }\left(f\right)\ge ch\left(f\right)-6+\frac{3}{2}\times 2=0$ 当f不与3⁻-点关联，则 $c{h}^{\prime }\left(f\right)\ge ch\left(f\right)-6+\frac{5}{4}\times 2+\frac{1}{2}>0$。

对于任意的 $v\in V\left(G\right)$，设 $d\left(v\right)=2$，则由R1， $c{h}^{\prime }\left(v\right)\ge 2ch\left(v\right)-6+1\times 2=0$。设 $d\left(v\right)=3$，则 $c{h}^{\prime }\left(v\right)=2\times ch\left(v\right)-6=0$。设 $d\left(v\right)=4$，则由R2， $c{h}^{\prime }\left(v\right)\ge 2\times ch\left(v\right)-6-\frac{1}{2}\times 4=0$。设 $d\left(v\right)=5$，则 $f_3\left(v\right)\le 3$，则由R3， $c{h}^{\prime }\left(v\right)\ge 2\times ch\left(v\right)-6-\frac{1}{2}\times 2-\frac{1}{3}\times 3=0$。设 $d\left(v\right)=6$，则 $f_3\left(v\right)\le 4$，当 $f_3\left(v\right)=4$，则 $f_5^{+}\left(v\right)=2$，由R4， $c{h}^{\prime }\left(v\right)\ge 2ch\left(v\right)-6-\frac{5}{4}\times 4-\frac{1}{3}\times 2>0$。当 $f_3\left(v\right)\le 3$， $c{h}^{\prime }\left(v\right)\ge 2ch\left(v\right)-6-\frac{5}{4}\times 3-\frac{3}{4}\times 3=0$。设 $d\left(v\right)=7$，则 $f_3\left(v\right)\le 4$，当 $f_3\left(v\right)=4$，则 $n_3\left(v\right)\le 1$， $f_5^{+}\left(v\right)\ge 2$，所以 $c{h}^{\prime }\left(v\right)\ge 2ch\left(v\right)-6-\frac{3}{2}\times 2-\frac{5}{4}\times 2-1-\frac{1}{3}\times 2>0$。当 $f_3\left(v\right)\le 3$，则 $f_5^{+}\left(v\right)\ge \text{1}$，所以 $c{h}^{\prime }\left(v\right)\ge 2ch\left(v\right)-6-\frac{3}{2}\times 3-1\times 3-\frac{1}{3}>0$。

设 $d\left(v\right)=8$，则 $n_2\left(v\right)\in \left\{0,1,2,\cdots 8\right\}$，下面开始分情况讨论。

情形1 $n_2\left(v\right)=0$，则 $f_3\left(v\right)\le 5$。

当 $f_3\left(v\right)\text{=}5$，则 $f_5^{+}\left(v\right)=3$，所以 $c{h}^{\prime }\left(v\right)\ge 2ch\left(v\right)-6-\frac{3}{2}\times 5-\frac{1}{3}\times 3>0$。当 $f_3\left(v\right)=4$，则 $f_4\left(v\right)\le 4$。若 $f_4\left(v\right)=4$，则 $n_3\left(v\right)\le 4$，所以至多有两个4-面关联两个3⁻-点，所以 $c{h}^{\prime }\left(v\right)\ge 2ch\left(v\right)-6-\frac{3}{2}\times 4-1\times 2-\frac{3}{4}\times 2>0$。若 $f_3\left(v\right)\le 3$，则 $ch\prime \left(v\right)\ge 2ch\left(v\right)-6-\frac{3}{2}\times 3-1\times 5>0$。

情形2 $n_2\left(v\right)=1$，则 $f_3\left(v\right)\le 5$。

当 $f_3\left(v\right)=5$，则 $f_5^{+}\left(v\right)=3$，所以 $c{h}^{\prime }\left(v\right)\ge 2ch\left(v\right)-6-1-\frac{3}{2}\times 5-\frac{1}{3}\times 3>0$。当 $f_3\left(v\right)=4$，若v关联两个相邻的3-面时，则 $f_5^{+}\left(v\right)\ge \text{2}$，所以 $c{h}^{\prime }\left(v\right)\ge 2ch\left(v\right)-6-1-\frac{3}{2}\times 4-1\times 2-\frac{1}{3}\times 2>0$。若与v关联的4个3-面两两不相邻，则 $n_3\left(v\right)=0$，所以 $c{h}^{\prime }\left(v\right)\ge 2ch\left(v\right)-6-1-\frac{3}{2}\times 1-\frac{5}{4}\times 3-\frac{3}{4}\times 4>0$。当 $f_3\left(v\right)\le 3$，则 $f_5^{+}\left(v\right)\ge 1$，所以 $c{h}^{\prime }\left(v\right)\ge 2ch\left(v\right)-6-1-\frac{3}{2}\times 3-1\times 4-\frac{1}{3}\times 1>0$。

情形3 $n_2\left(v\right)=2$，则 $f_3\left(v\right)\le 4$。

当 $f_3\left(v\right)=4$，则 $f_5{}^{+}\left(v\right)=4$，所以 $c{h}^{\prime }\left(v\right)\ge 2ch\left(v\right)-6-2-\frac{3}{2}\times 4-\frac{1}{3}\times 4>0$。当 $f_3\left(v\right)=3$，若v关联两个相邻的3-面时，则 $f_5^{+}\left(v\right)\ge 3$，所以 $c{h}^{\prime }\left(v\right)\ge 2ch\left(v\right)-6-2-\frac{3}{2}\times 3-1\times 2-\frac{1}{3}\times 3>0$。若与v关联的3-面两两不相邻，则点v关联的4-面至多关联一个3⁻-点，所以 $c{h}^{\prime }\left(v\right)\ge 2ch\left(v\right)-6-2-\frac{3}{2}\times 3-\frac{3}{4}\times 4-\frac{1}{3}\times 1>0$。当 $f_3\left(v\right)\le 2$，则 $f_4\left(v\right)\le 4$，所以 $c{h}^{\prime }\left(v\right)\ge 2ch\left(v\right)-6-2-\frac{3}{2}\times \text{2}-\text{1}\times \text{4}-\frac{\text{1}}{\text{3}}\times \text{2}>0$。

情形4 $n_2\left(v\right)=3$，则 $f_3\left(v\right)\le 3$。

当 $f_3\left(v\right)=3$，则 $f_5^{+}\left(v\right)\ge \text{2}$， $f_6^{+}\left(v\right)\ge \text{1}$， $f_4\left(v\right)\le 2$，且点v关联的4-面至多关联一个3⁻-点，所以 $c{h}^{\prime }\left(v\right)\ge 2ch\left(v\right)-6-3-\frac{3}{2}\times 3-\frac{3}{4}\times 2-\frac{1}{3}\times 2>0$。当 $f_3\left(v\right)\le 2$，则 $f_4\left(v\right)\le 3$，若 $f_4\left(v\right)=3$，则与点v关联的4-面中至少有一个四面至多关联一个3⁻-点，所以 $c{h}^{\prime }\left(v\right)\ge 2ch\left(v\right)-6-3-\frac{3}{2}\times 2-1\times 2-\frac{3}{4}\times 1-\frac{1}{3}\times 3>0$。若 $f_4\left(v\right)\le 2$，则 $c{h}^{\prime }\left(v\right)\ge 2ch\left(v\right)-6-3-\frac{3}{2}\times 2-1\times 2-\frac{1}{3}\times 4>0$。

情形5 $n_2\left(v\right)=4$，则 $f_3\left(v\right)\le 2$。

当 $f_3\left(v\right)=2$，则 $f_4\left(v\right)\le 4$。若 $f_4\left(v\right)=4$，则点v不与3⁻-点相邻，所以 $c{h}^{\prime }\left(v\right)\ge 2ch\left(v\right)-6-4-\frac{5}{4}\times 2-1\times 2-\frac{3}{4}\times 4>0$。若 $f_4\left(v\right)\le 3$，则与点v关联的4-面中至少有两个4-面至多关联一个3⁻-点，所以 $c{h}^{\prime }\left(v\right)\ge 2ch\left(v\right)-6-4-\frac{3}{2}\times 2-1-\frac{3}{4}\times 2-\frac{1}{3}>0$。

当 $f_3\left(v\right)=1$，则 $f_4\left(v\right)\le 4$，且 $f_6^{+}\left(v\right)\ge 1$。若 $f_4\left(v\right)=4$，则 $f_6^{+}\left(v\right)=1$，且与点v关联的4-面中至少有两个4-面至多关联一个3⁻-点，所以 $c{h}^{\prime }\left(v\right)\ge 2ch\left(v\right)-6-4-\frac{3}{2}\times 1-1\times 2-\frac{3}{4}\times 2-\frac{1}{3}\times 2>0$。若 $f_4\left(v\right)\le 3$，则 $f_6^{+}\left(v\right)\ge 1$，所以 $c{h}^{\prime }\left(v\right)\ge 2ch\left(v\right)-6-4-\frac{3}{2}\times 1-1\times 3-\frac{1}{3}\times 3>0$。当 $f_3\left(v\right)=0$，则 $f_4\left(v\right)\le 4$，所以 $c{h}^{\prime }\left(v\right)\ge 2ch\left(v\right)-6-4-1\times 4-\frac{1}{3}\times 4>0$。

情形6 $n_2\left(v\right)=5$，则 $f_3\left(v\right)\le 2$。

当 $f_3\left(v\right)=2$，则 $f_4\left(v\right)=0$，且 $f_6^{+}\left(v\right)\ge 4$，所以 $c{h}^{\prime }\left(v\right)\ge 2ch\left(v\right)-6-5-\frac{3}{2}\times 2-\frac{1}{3}\times 2>0$。

当 $f_3\left(v\right)=1$，则 $f_4\left(v\right)\le 3$，且 $f_6^{+}\left(v\right)\ge 3$，所以 $c{h}^{\prime }\left(v\right)\ge 2ch\left(v\right)-6-5-\frac{3}{2}\times 1-1\times 3-\frac{1}{3}>0$。

当 $f_3\left(v\right)=0$，则 $f_4\left(v\right)\le 3$，且 $f_6^{+}\left(v\right)\ge 2$，所以 $c{h}^{\prime }\left(v\right)\ge 2ch\left(v\right)-6-5-1\times 3-\frac{1}{3}\times 3>0$。

情形7 $n_2\left(v\right)=6$，则 $4\le f_6^{+}\left(v\right)\le 5$。

当 $f_6^{+}\left(v\right)=4$，则 $f_3\left(v\right)=0$，且 $f_4\left(v\right)\le 2$，所以 $c{h}^{\prime }\left(v\right)\ge 2ch\left(v\right)-6-6-1\times 2-\frac{1}{3}\times 2>0$。

当 $f_6^{+}\left(v\right)=5$，则 $f_3\left(v\right)\le 1$，且 $f_4\left(v\right)\le 2$，所以 $c{h}^{\prime }\left(v\right)\ge 2ch\left(v\right)-6-6-\frac{3}{2}\times 1-1\times 2>0$。

情形8 $n_2\left(v\right)\ge 7$，则 $f_3\left(v\right)=0$，且 $f_4\left(v\right)\le 3$， $f_6^{+}\left(v\right)\ge 6$，所以 $c{h}^{\prime }\left(v\right)\ge 2ch\left(v\right)-6-8-1-\frac{1}{3}>0$。

至此，定理的证明完成。

基金项目

本课题由山东省自然科学基金：ZR2020MA045资助。

NOTES

^*第一作者。

^#通讯作者。