青岛大学数学与统计学院，山东 青岛

收稿日期：2021年7月9日；录用日期：2021年8月12日；发布日期：2021年8月19日

摘要

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

关键词

欧拉示性数，曲面，全染色，权转移方法

Total Coloring of Embedded Graphs with Maximum Degree at Least Eight

Liting Wang^*, Huijuan Wang^#

School of Mathematics and Statistics, Qingdao University, Qingdao Shandong

Received: Jul. 9^th, 2021; accepted: Aug. 12^th, 2021; published: Aug. 19^th, 2021

ABSTRACT

Graph coloring is an important research direction in graph theory. It has very important applications 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.

Keywords:Euler Characteristic, Surface, Total Coloring, Discharging Method

Copyright © 2021 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

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]。

图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资助。

文章引用

王丽婷,王慧娟. 最大度大于等于八的可嵌入图的全染色
Total Coloring of Embedded Graphs with Maximum Degree at Least Eight[J]. 理论数学, 2021, 11(08): 1505-1510. https://doi.org/10.12677/PM.2021.118169

参考文献