平面图的无圈5-可选性

Acyclic 5-Choosability of Planar Graph

摘要: 假设Φ是图G的一个顶点染色。如果任意两个相邻的点染不同颜色，且每个圈至少使用三种颜色，则称Φ是一个无圈染色。如果对于G的任意的k-列表配置L，G有一个无圈L-染色，则称G是无圈k-可选的。本文证明了3圈不与i(i=3,7,9)圈相邻和4圈不与j(3≤j≤6)圈相邻的平面图是无圈5-可选的。

Abstract: Let Φ is a vertex coloring of graph G. The Φ is acyclic if two adjacent vertices color with different colors and every cycle uses at least three colors. A graph G is k-acyclicallychoosable if G is acyclic L-list colorable for any list assignment L with ▏L(v)▏≥k for each v∈V(G). In this paper, we prove that a planar graph is acyclically 5-choosable if it does not contain an i-cycle adjacent to a j-cycle, where j=3,7,9 if i=3 and 3≤j≤6 if i=4.

1. 引言

设G是一个具有顶点集V(G)和边集E(G)的图。G的一个正常的k-染色是一个映射 $\varphi$ ： $V\left(G\right)\to \left\{1,2,\cdots ,k\right\}$ ，使得对于任何边 $xy\in E\left(G\right)$ 有 $\varphi \left(x\right)\ne \varphi \left(y\right)$ 。如果每个圈使用至少三种颜色。则称 $\varphi$ 是一个无圈k-染色。如果G有一个无圈k-染色，则称G是一个无圈k-可染的。

1973年Grünbaum在文献 [1] 提出猜想：每个平面图都是无圈5-可染的。Borodin在文献 [2] 证明了Grünbaum的猜想。1976年，Kostochka等人在文献 [3] 证明了存在二部2-退化的平面图，它们不是无圈4-可染的。所以这个界5是最好的。

图G的一个列表配置L是为G的每个顶点v分配一个可选颜色集 $L\left(v\right)$ 。如果G有一个正常的染色 $\varphi$ ，使得对每个顶点v， $\varphi \left(x\right)\in L\left(x\right)$ ，那么图G是L列表可染的。如果对每个顶点v， $\left|L\left(v\right)\right|\ge k$ ，则称L是一个k-列表配置。如果对于G的任意的k-列表配置L，G都是L-可染的，则称G是k-可选的。如果对于G的任意的k-列表配置L，G有一个无圈L-染色，则称G是无圈k-可选的。G的无圈列表色数是使得G是无圈k可选的最小的整数k。对于平面图得可选性，我们可以知道以下一些结果。

因为每个子图都有一个最多为5度的顶点，所以每个平面图都是6-可选的，这是显然的。1993年Voigt在文献 [4] 中给出了一个不是4-可选的平面图的例子。之后Thomassen在文献 [5] 中证明了每个平面图都是5-可选的。这也就论证了平面图是5-可选的。通过平面图的可选性，下面扩展到无圈可选性。

对于列表无圈染色，早在2002年Borodin等人在文献 [6] 中证明了所有平面图都是无圈7-可选的，并提出了以下猜想：

猜想1 每个平面图都是无圈5-可选的。

这个猜想是困难的，关于这个猜想很多人做了尝试。在2011年之前，它只验证了几个限制类的平面图：围长至少5 [7] ，没有4和5圈，或没有4和6圈 [8] ，没有4圈和弦6圈 [9] ，没有4圈也没有两个3圈的距离小于3 [10] 。在所有这些结果中，长度为4的圈都是被禁止的。2011年，Borodin和Ivanova在文献 [11] 中证明了3圈不与 $i\left(3\le i\le 5\right)$ 圈相邻和4圈不与 $j\left(4\le j\le 6\right)$ 圈相邻的平面图是无圈5-可选的。2013年，Borodin等人在文献 [12] 中证明了没有4圈和5圈的平面图是无圈4-可选的。2014年，Wang等人在文献 [13] 中证明了4圈不与 $i\left(i=3,4,5,6\right)$ 圈相邻的平面图是无圈6-可选的。同年，Hou和Liu在文献 [14] 中证明了每个环形图是无圈8-可选的。2021年，Sun lin在在文献 [15] 中证明了没有5圈和相邻4圈的平面图是无圈6-可选的。本文在这些基础上进行了拓展：

定理1 3圈不与 $i\left(i=3,7,9\right)$ 圈相邻和4圈不与 $j\left(3\le j\le 6\right)$ 圈相邻的平面图是无圈5-可选的。

本篇文章中所有的图都是有限简单图。对于一个平面图G， $V\left(G\right)$ ， $E\left(G\right)$ ， $F\left(G\right)$ 是图G的点，边，面的集合。对于 $v\in V\left(G\right)$ ， $N_G\left(v\right)$ (或简单地用 $N\left(v\right)$ 来表示)表示v的邻居的集合，并且 $d_G\left(v\right)=\left|N_G\left(v\right)\right|$ (或简单地用 $d\left(v\right)$ 来表示)是v的度。假设 $N_G\left[v\right]=N_G\left(v\right)\cup \left\{x\right\}$ 。如果两个圈或者面至少有一个公共点，那么我们说他们是相交的。如果两个圈或者面至少有一条公共边，那么我们说他们是相邻的。如果 $u_1,u_2,\cdots ,u_n$ 是f上按照顺时针的顺序的边界上的点，那么我们用 $\left[u_1{u}_2\cdots u_n\right]$ 去表示一个面f，并且允许有重复的点。一个面f的度是其边界漫游中的边步数，用 $d_G\left(f\right)$ 表示。一个k-点，k^--点，或者k⁺-点是一个k度，至少k度，或者至多k度的点。我们同样可以定义k-面，k^--面，k⁺-面。

对于 $x\in V\left(G\right)\cup F\left(G\right)$ 并且 $i\ge 2$ ， $n_i\left(x\right)$ 表示与x相邻或者相关联的i-点的数量。如果一个点或者一条边与一个3-面相关联，那么它被称为三角形的。如果uv是一条不是三角形的边，并且u是一个三角形的3-点，那么称u是v的坏的邻居。

2. 定理1的证明

设G是定理1的极小反例，就是说对于 $v\in V\left(G\right)$ 有一个 $\left|L\left(v\right)\right|\ge 5$ 的列表配置L，使得G不是无圈L-染色，而对于 $\left|V^{\prime }\left(G\right)\right|<\left|V\left(G\right)\right|$ 的任何子图 $V^{\prime }\left(G\right)$ 是无圈L-染色。显然，G是连通的并且没有1-点。

2.1. 极小反例的结构性质

以下极小反例的结构性质的证明在文献 [4] [5] [10] 中。

引理1 对于每个 $v\in V\left(G\right)$ ，G有以下性质。

(A1) 一个2-点不与一个4⁻-点相邻。

(A2) 如果 $d\left(v\right)=3$ ，那么

(i) v没有坏的邻居，并且

(i) 如果v与一个3-点相邻，那么v不会与任何4⁻-点相邻。

(A3) 4-点没有坏的邻居。

(A4) 如果 $d\left(v\right)=5$ ，那么

(i) $n_2\left(v\right)\le 1$ ，并且

(i) 如果 $n_2\left(v\right)=1$ ，那么v不会与任何三角形的3-点相邻。

(A5) 如果 $d\left(v\right)=6$ ，那么

(i) $n_2\left(v\right)\le 4$ ，而且

(i) 如果 $n_2\left(v\right)=4$ ，那么v既不与一个3-点相邻也不与一个3-面相关联。

(A6) 如果 $d\left(v\right)=7$ ，那么 $n_2\left(v\right)\le 5$ 。

(A7) 不会存在一个3-面 $xyz$ 使得 $d\left(x\right)=3$ ， $d\left(y\right)\le 4$ 和 $d\left(z\right)\le 4$ 。

2.2. 权转移

由欧拉公式 $\left|V\right|-\left|E\right|+\left|F\right|=2$ 和公式 ${\displaystyle \underset{v\in V}{\sum }{d}_G\left(v\right)}=2\left|E\right|={\displaystyle \underset{f\in F}{\sum }{d}_G}\left(f\right)$ 。我们可以得出

${\displaystyle \underset{v\in V}{\sum }\left(d_G\left(v\right)-4\right)}+{\displaystyle \underset{f\in F}{\sum }\left(d_G\left(f\right)-4\right)}=-8$ 。

现在我们对每个 $x\in V\cup F$ 定义一个初始权重 $ch\left(x\right)$ ，设对每个 $v\in V$ ， $ch\left(v\right)=d_G\left(v\right)-4$ ，每个 $f\in F$ ， $ch\left(f\right)=d_G\left(f\right)-4$ 。我们将设计适当的权转移规则。由于权转移过程中，总的权值是固定的，如果我们将初始权值 $ch\left(x\right)$ 改变为最终权值 $c{h}^{\prime }\left(x\right)$ ，使得对于每个 $x\in V\cup F$ ，都满足 $c{h}^{\prime }\left(x\right)\ge 0$ ，那么

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

这将是一个矛盾。这意味着定理中的反例不存在，因此定理成立。

权转移规则如下：

R1每个10⁺-面给3-面转权 $\frac{1}{2}$ 。

R2每个2-点v的邻居给2-点$v$转权 $\frac{1}{2}$ ，并且如果v不与一个4-面相关联，那么与v相关联的5⁺-面给v转权 $\frac{1}{2}$ ，否则与v相关联的7⁺-面给v转权1。

如果5-面与一个2-点和两个非三角形的3-点相关联，那么我们称5-面是虚弱的。

R3如果5⁺-面是虚弱的，那么5⁺-面给每个相关联的非三角形的3-点转权 $\frac{1}{4}$ 。如果3-点与4-面相关联，那么5⁺-面给每个相关联的非三角形的3-点转权 $\frac{1}{2}$ 。如果3-点与其他面相关联，那么5⁺-面给每个相关联的非三角形的3-点转权 $\frac{1}{3}$ 。

R4每个5-面给三角形的3-点转权 $\frac{1}{4}$ ，每个10⁺-面给三角形的3-点转权 $\frac{1}{2}$ 。

R5 5⁺-点给每个相邻的三角形的3-点转权 $\frac{1}{6}$ 。

R6如果5⁺-点与非三角形的3-点相邻，且非三角形的3-点与虚弱的5-面相关联，那么5⁺-点给非三角形的3-点转权 $\frac{1}{8}$ 。

因为G中3圈不与 $i\left(i=3,7,9\right)$ 圈相邻和4圈不与 $j\left(3\le j\le 6\right)$ 圈相邻，所以我们有如下命题。

命题1 1) 当5-面与3-面中的某一边相邻时，3-面的另外两边都与10⁺-面相邻。

2) 3-面不与6-面和8-面相邻。

3) 4-面与7⁺-面相邻。

下面将检验对于所有的 $v\in V\left(G\right)$ ， $c{h}^{\prime }\left(x\right)\ge 0$ 。

情况1： $d\left(v\right)=2$ 。

在这种情况下，我们有 $ch\left(v\right)=2-4=-2$ 。根据引理1 (A1)和R2，则 $c{h}^{\prime }\left(v\right)\ge ch\left(v\right)+2\times \frac{1}{2}+1=0$ 。

情况2： $d\left(v\right)=3$ 。

在这种情况下，我们有 $ch\left(v\right)=3-4=-1$ 。如果v与一个3-面uvw相关联并且与一个不是u，w的点z相邻，那么根据引理1 (A3)， $d\left(z\right)\ge 5$ ，并且根据引理1 (A7)，u，w中至少有一点的度大于等于5。由此 $c{h}^{\prime }\left(v\right)\ge ch\left(v\right)+2\times \frac{1}{6}+\frac{1}{2}+\frac{1}{4}>0$ 。如果v与一个4-面相关联，那么根据命题1和R3， $c{h}^{\prime }\left(v\right)\ge ch\left(v\right)+2\times \frac{1}{2}>0$ 。如果v在虚弱的5-面的边界上，那么根据R3和R6， $c{h}^{\prime }\left(v\right)\ge ch\left(v\right)+2\times \frac{1}{8}+\frac{1}{3}+2\times \frac{1}{4}>0$ 。这是因为根据引理1 (F2)，v至少跟两个5⁺-点相邻，因此v最多与两个虚弱的5-面相关联。否则， $c{h}^{\prime }\left(v\right)\ge ch\left(v\right)+3\times \frac{1}{3}=0$ 。

情况3： $d\left(v\right)=4$ 。

显然， $c{h}^{\prime }\left(v\right)=ch\left(v\right)=0$ 。

情况4： $d\left(v\right)=5$ 。

在这种情况下， $ch\left(v\right)=5-4=1$ 。根据引理1 (A4)，有 $n_2\left(v\right)\le 1$ 。如果 $n_2\left(v\right)=0$ ，那么根据R5和R6， $c{h}^{\prime }\left(v\right)\ge ch\left(v\right)-5\times \frac{1}{6}>0$ 。假设 $n_2\left(v\right)=1$ ，根据引理1 (A4)，$v$不与三角形的3-点相邻。因此根据R2和R6， $c{h}^{\prime }\left(v\right)\ge ch\left(v\right)-4\times \frac{1}{8}-\frac{1}{2}=0$ 。

情况5： $d\left(v\right)\ge 6$ 。

当 $d\left(v\right)=6$ 时，根据引理1 (A5)，有 $n_2\left(v\right)\le 4$ 。如果 $n_2\left(v\right)=4$ ，那么根据引理1 (A5)，v不与3-点相邻。则 $c{h}^{\prime }\left(v\right)\ge 6-4-4\times \frac{1}{2}=0$ 。如果 $n_2\left(v\right)\le 3$ ，那么 $c{h}^{\prime }\left(v\right)\ge 6-4-3\times \frac{1}{2}-3\times \frac{1}{6}=0$ 。

当 $d\left(v\right)=7$ 时，根据引理1 (A6)，有 $n_2\left(v\right)\le 5$ 。则 $c{h}^{\prime }\left(v\right)\ge 7-4-5\times \frac{1}{2}-2\times \frac{1}{6}>0$ 。

当 $d\left(v\right)\ge 8$ 时， $c{h}^{\prime }\left(v\right)\ge d\left(v\right)-4-d\left(v\right)\times \frac{1}{2}=\frac{1}{2}d\left(v\right)-4\ge 0$ 。

下面将检验对于所有的 $f\in F\left(G\right)$ ， $c{h}^{\prime }\left(f\right)\ge 0$ 。

情况1： $d\left(f\right)\le 4$ 。

当 $d\left(f\right)=3$ 时，如果5-面与$f$相邻s，那么根据R1，有 $c{h}^{\prime }\left(f\right)\ge 3-4+2\times \frac{1}{2}=0$ 。否则有 $c{h}^{\prime }\left(f\right)\ge 3-4+3\times \frac{1}{2}>0$ 。

当 $d\left(f\right)=4$ 时，有 $c{h}^{\prime }\left(f\right)=ch\left(f\right)=0$ 。

情况2： $d\left(f\right)=5$ 。

在这种情况下， $ch\left(f\right)=5-4=1$ 。根据引理1 (A1)，有 $n_2\left(f\right)\le 2$ 。如果 $n_2\left(f\right)=2$ ，根据R2，那么 $c{h}^{\prime }\left(f\right)\ge 1-2\times \frac{1}{2}=0$ 。如果 $n_2\left(f\right)=1$ ，那么 $n_3\left(f\right)\le 2$ 。如果有两个3-点，根据R2，R3和R4，那么 $c{h}^{\prime }\left(f\right)\ge 1-2\times \frac{1}{4}-\frac{1}{2}=0$ 。如果至多一个3-点，根据R2，R3和R4，那么 $c{h}^{\prime }\left(f\right)\ge 1-\frac{1}{3}-\frac{1}{2}>0$ 。如果 $n_2\left(f\right)=0$ ，那么 $n_3\left(f\right)\le 3$ 。根据R2，R3和R4， $c{h}^{\prime }\left(f\right)\ge 1-3\times \frac{1}{3}=0$ 。

情况3： $d\left(f\right)\ge 6$ 。

为了估计f总的转权，我们将f的转权均匀地分配给f的边界中最接近转权接受者的边中的相关联的小于等于的3个顶点和相邻的3个面。

已知通过R2一个2-点最多从f得到权重1，通过R3和R4一个3-点最多从f得到权重 $\frac{1}{2}$ ，f最多给每个相邻的3-面转权 $\frac{1}{2}$ 。

很容易看出，来自f的每个权中的接收者都恰好属于以下三种类型的一条路径P，其中指数取模 $d\left(f\right)$ ：

i) $v_i{v}_{i+1}{v}_{i+2}$ ，其中 $d\left(v_i\right)>3$ ， $d\left(v_{i+1}\right)\le 3$ ， $d\left(v_{i+2}\right)>3$ ，并且 $v_{i+1}$ 是非三角形的；

ii) $v_i\cdot \cdot \cdot v_{i+3}$ ，其中 $v_{i+1}$ 和 $v_{i+2}$ 是非三角形的， $d\left(v_i\right)>3$ ， $d\left(v_{i+1}\right)=d\left(v_{i+2}\right)=3$ ， $d\left(v_{i+3}\right)>3$ ；

iii) 极大序列 $v_i\cdot \cdot \cdot v_{i+k}$ 由三角形边组成，其中 $k\ge 1$ ，由（非三角形）边 $v_{i-1}v$ 或 $v_{i+k}{v}_{i+k+1}$ 扩张当且仅当 $d\left(v_i\right)=3$ 或者 $d\left(v_{i+k}\right)=3$ 。

设P由l(P)条边组成，并通过R1~R3导致f的总转权m(P)。如果P是类型iii)，则 $m\left(P\right)=l\left(P\right)/2$ ，这意味着P的每条边在平均后从f中转权 $\frac{1}{2}$ 得到。如果P的类型是ii)，那么 $l\left(P\right)=3$ 并且 $m\left(P\right)=\frac{2}{3}$ ，所以P的每条边平均从f中最多得到 $\frac{2}{9}$ 。

假设P的类型是i)；然后是 $l\left(P\right)=2$ 并且 $m\left(P\right)\le 1$ ；所以P的每条边从f中最多得到 $\frac{1}{2}$ 。此外，当且仅当 $d\left(v_{i+1}\right)=2$ 并且 $d\left(v_{i+1}\right)$ 与4-面相关联时， $m\left(P\right)=1$ 。否则， $m\left(P\right)=\frac{1}{3}$ ，所以P的两条边从f中得到 $\frac{1}{6}$ 。

由于我们的反例G的结构性质A1~A7，f的边界中的每条边最多属于一条i)~iii)类型的路径。

如果 $d\left(f\right)=6$ ，那么根据定理1的假设，具有 $m\left(P\right)=1$ 的路径P是不可能的，所以 $c{h}^{\prime }\left(f\right)\ge 6-4-6\times \frac{1}{3}=0$ 。

如果 $d\left(f\right)=7$ ，那么f具有 $m\left(P\right)=1$ 的路径P最多有3条。当 $m\left(P\right)=1$ 的路径P最多有2条时， $c{h}^{\prime }\left(f\right)\ge 7-4-4\times \frac{1}{2}-\left(7-4\right)\times \frac{1}{3}=0$ 。当 $m\left(P\right)=1$ 的路径P有3条时， $c{h}^{\prime }\left(f\right)\ge 7-4-6\times \frac{1}{2}=0$ 。

如果 $8\le d\left(f\right)\le 9$ ，那么 $c{h}^{\prime }\left(f\right)\ge d\left(f\right)-4-\frac{1}{2}d\left(f\right)\ge 0$ 。

如果 $d\left(f\right)\ge 10$ ，那么我们记类型(i)的路径的总边数为 $a\left(P\right)$ ，类型(ii)的路径的总边数为 $b\left(P\right)$ ，类型iii)的路径的总边数为 $c\left(P\right)$ 。则我们有 $a\left(P\right)+b\left(P\right)+c\left(P\right)\le d\left(f\right)$ 。所以

$\begin{array}{c}c{h}^{\prime }\left(f\right)\ge d\left(f\right)-4-\frac{1}{2}a\left(P\right)-\frac{2}{9}b\left(P\right)-\frac{1}{2}c\left(P\right)\\ \ge d\left(f\right)-4-\frac{1}{2}d\left(f\right)+\frac{1}{2}b\left(P\right)-\frac{2}{9}b\left(P\right)\\ =\frac{1}{2}d\left(f\right)-4+\frac{5}{18}b\left(P\right)\\ \ge \frac{1}{2}d\left(f\right)-4\\ \ge 0\end{array}$

定理1证毕。

3. 总结与展望

本文采用定理证明与权转移相结合的方法证明定理。权转移方法是图的染色理论中常用的证明方法之一，权转移方法经常结合其他方法和技术，如组合数学中的一些组合方法，在证明很多与染色问题有关的命题时，应用非常广泛，方法非常巧妙。当然该方法也有局限性，对于权转移的讨论过程比较繁琐。本文对于平面图是无圈5-可选的猜想更进了一步，允许了4-圈存在，图类更加广泛。在今后的研究中将会继续专研平面图是无圈5-可选的猜想，证明方法进一步改进，减少繁琐的过程，尽量精简过程。