不含相邻三角形平面图的全群可选性

Total Group Choosability of Planar Graphs without Adjacent Triangles

摘要: 如果对于阶数至少为k的阿贝尔群A和任意k列表分配L:V→2^A，G都是(A,L)可染的，则称图G是k群可选的。G的群选择数是使得G是k群可选的数k的最小值。图G的全图T(G)的群选择数称为G的全群选择数。本文主要研究平面图的全群列表染色，利用结构分析法和Discharging方法，得到了两类不含相邻三角形的特殊平面图的全群选择数的上界。

Abstract: If for any group A of order at least k and any k-list assignment L:V→2^A, G is (A,L)-colorable, then we say that G is k-group choosable. The group choice number of G is the smallest k such that G is k-group choosable. The group choice number of the total graph T(G) of the graph G is called the total group choice number of G. In this paper, we mainly study the total group list coloring of planar graphs. By using the structural analysis and the Discharging method, we obtained upper bounds on the number of total group choices for two classes of special planar graphs without adjacent triangles.

1. 引言

本文所考虑的图均为有限简单图，未定义的术语和符号参见文献 [1] 。设G是一个图，分别用 $V\left(G\right)$ 、 $E\left(G\right)$ 、 $\Delta \left(G\right)$ 和 $\delta \left(G\right)$ (或简单地用V、E、 $\Delta$ 和 $\delta$ )表示图G的顶点集、边集、最大度和最小度。有向图G的定向D是指赋予G的每条边一个方向。如果图G可以画在平面上，使它的边仅在端点处相交，则称G为平面图，且用 $F\left(G\right)$ (或简单地用F)表示G的面集。设 $v\in V\left(G\right)$ ，与v相关联的边的数目叫做v的度，记作 $d\left(v\right)$ 。设 $f\in F\left(G\right)$ ，与f相关联的边的数目(每条割边计算两次)叫做f的度，记作 $d\left(f\right)$ 。 $k^{+}$ -点，k-点， $k^{-}$ -点分别指度不小于k，等于k和不大于k的顶点。可类似定义 $k^{+}$ -面，k-面， $k^{-}$ -面。长度为k的圈称为k圈。如果两个圈至少有一条公共边，则称它们是相邻的。一般情况下，3圈也被称为三角形。

图G的k点染色是从 $V\left(G\right)$ 到 $\left\{1,2,\cdots ,k\right\}$ (颜色集)的一个映射，使得任意两个相邻顶点的颜色不同。如果图G有k点染色，则称G是k可染的。G的色数 $\chi \left(G\right)$ 是使得G是k可染的数k的最小值。列表染色是由点染色发展而来，Erdös等人于1979年在文献 [2] 中给出了列表染色的定义。如果映射L为图G的每个顶点v提供可能的颜色列表 $L\left(v\right)$ ，则映射L被称为G的列表分配。G的k列表分配L是指对于G的每个顶点均有 $\left|L\left(v\right)\right|=k$ 的列表分配。设L是图G的一个列表分配，如果存在G的点染色c，使得对于G的每一个顶点v都有 $c\left(v\right)\in L\left(v\right)$ ，那么称G是L可染的。如果对于图G的每一个k列表分配L，G都是L可染的，则称G是k可选的。图G的选择数(或称列表色数) ${\chi }_l\left(G\right)$ 是使得G是k可选的数k的最小值。学者们对图的列表染色进行了广泛的研究，并取得了一系列的成果，可参见文献 [3] - [8] 。

图的群染色是由Jaeger等人于1992年在文献 [9] 中所提出的。设G是一个图，A是一个阿贝尔群，记 $F\left(G,A\right)$ 为所有E到A的映射组成的集合，设D为G的一个定向，如果对于每一个 $f\in F\left(G,A\right)$ ，都存在顶点染色 $c:V\to A$ ，使得 $c\left(u\right)-c\left(v\right)\ne f\left(uv\right)$ ，其中边uv的方向是由u指向v，则称图G是A可染的。设A是任意阶至少为k的阿贝尔群，使得G是A可染的数k的最小值称为G的群色数，记为 ${\chi }_g\left(G\right)$ 。

图的群列表染色是由列表染色和群染色进一步拓展而来。设G是一个图，A是一个阶数至少为k的阿贝尔群，设D为G的一个定向， $L:V\to 2^A$ 为G的列表分配。对于 $f\in F\left(G,A\right)$ ，图G的 $\left(A,L,f\right)$ 染色是指G的染色 $c:V\to A$ 满足对于 $\forall v\in V$ 有 $c\left(v\right)\in L\left(v\right)$ 且 $c\left(u\right)-c\left(v\right)\ne f\left(uv\right)$ ，其中边uv方向是由u指向v。如果对于每个 $f\in F\left(G,A\right)$ ，都存在G的 $\left(A,L,f\right)$ 染色，那么称G是 $\left(A,L\right)$ 可染的。Král等人在文献 [10] 中引入了群可选性的概念。如果对于阶数至少为k的阿贝尔群A和任意k列表分配 $L:V\to 2^A$ ，G都是 $\left(A,L\right)$ 可染的，则称图G是k群可选的。G的群选择数是使得G是k群可选的数k的最小值，记为 ${\chi }_g{}_l\left(G\right)$ 。群可选性受到学者们的广泛关注，并且已得到该领域的一些初步结果 [11] [12] [13] [14] [15] 。

图G的全图 $T\left(G\right)$ 是以G的顶点集 $V\left(G\right)$ 和边集 $E\left(G\right)$ 作为顶点集，即 $V\left(T\left(G\right)\right)=V\left(G\right)\cup E\left(G\right)$ 。在 $T\left(G\right)$ 中顶点u和顶点v相邻当且仅当满足以下三种情形之一：

1) $u\in V\left(G\right)$ ， $v\in V\left(G\right)$ ，并且 $uv\in E\left(G\right)$ ，即在G中顶点u和顶点v相邻；

2) $u\in V\left(G\right)$ ， $v\in E\left(G\right)$ ，并且在G中边v关联顶点u；

3) $u\in E\left(G\right)$ ， $v\in E\left(G\right)$ ，并且在G中边u和边v相邻。

图G的全色数 ${\chi }^{″}\left(G\right)$ 是指全图 $T\left(G\right)$ 的色数，即 ${\chi }^{″}\left(G\right)=\chi \left(T\left(G\right)\right)$ ；图G的列表全色数 ${{\chi }^{″}}_l\left(G\right)$ 是指全图 $T\left(G\right)$ 的列表色数，即 ${{\chi }^{″}}_l\left(G\right)={\chi }_l\left(T\left(G\right)\right)$ ；图G的全图 $T\left(G\right)$ 的群色数称为G的全群色数，记为 ${{\chi }^{″}}_g\left(G\right)$ ，即 ${{\chi }^{″}}_g\left(G\right)={\chi }_g\left(T\left(G\right)\right)$ 。图G的全图 $T\left(G\right)$ 的群选择数是使得 $T\left(G\right)$ 是k群可选的数k的最小值，记为 ${\chi }_g{}_l\left(T\left(G\right)\right)$ 。图G的全图 $T\left(G\right)$ 的群列表色数称为G的全群列表色数，记为 ${{\chi }^{″}}_{gl}\left(G\right)$ ，即有 ${{\chi }^{″}}_{gl}\left(G\right)={\chi }_{gl}\left(T\left(G\right)\right)$ 。在文献 [16] 中，赖虹建等人将全染色和列表全染色的概念扩展到图的全群染色和列表全群染色，并研究了两种平面图的全群列表染色，证明了：设G是 $\Delta \left(G\right)\le k\left(k\ge 6\right)$ 的平面图，若G不包含4圈或5圈，则 ${{\chi }^{″}}_{gl}\left(G\right)\le k+2$ ；设G是 $\Delta \left(G\right)\le k\left(k\ge 5\right)$ 的平面图，若G不包含4圈和5圈，则 ${{\chi }^{″}}_{gl}\left(G\right)\le k+2$ 。

2. 主要结果及证明

在本文定理的证明中，我们采用反证法，通过构造极小反例，分析极小反例的结构性质，利用Discharging方法进行证明。首先对欧拉公式进行变形，得到顶点和面的初始权值 $ch\left(x\right)$ $\left(x\in V\cup F\right)$，且有 ${\displaystyle \underset{x\in V\cup F}{\sum }ch\left(x\right)}<0$ 。其次构建权转移规则，对顶点和面的权值进行转移，使得顶点和面的新权值 $c{h}^{\prime }\left(x\right)$ 均非负，即 $c{h}^{\prime }\left(x\right)\ge 0$ $\left(x\in V\cup F\right)$，从而 ${\displaystyle \underset{x\in V\cup F}{\sum }c{h}^{\prime }\left(x\right)}\ge 0$ 。这与权转移过程中权的总量保持不变相矛盾，说明极小反例不存在，从而完成证明。

如果面f的边界是一个圈，那么称f是简单面。我们用 $m_v\left(f\right)$ 表示面f按顺时针方向通过顶点v的次数。显然，如果顶点v不是割点，或者面f是一个简单面，那么 $m_v\left(f\right)=1$ 。若顶点v是一个与非简单面f相关联的割点，则v的权转移过程等价于v与 $m_v\left(f\right)$ 个 $d\left(f\right)$ 面相关联的情形；类似地，若面f是与割点v相关联的非简单面，则f的权转移过程等价于f与 $m_v\left(f\right)$ 个 $d\left(v\right)$ 点关联的情形。因此，在下文计算新权的过程中，我们总假定v不是割点，并且面f是简单面。

定理2.1设G是 $\Delta \le k$ ( $k\ge 8$ )且不含相邻三角形的平面图，则 ${{\chi }^{″}}_{gl}\left(G\right)\le k+2$ 。

证明反证法。设G是满足定理2.1条件的 $\left|V\right|+\left|E\right|$ 最小的反例，则存在阿贝尔群A( $\left|A\right|\ge k+2$ )， $\left(k+2\right)$ 列表分配 $L:V\left(T\left(G\right)\right)\to 2^A$ 和 $f\in F\left(T\left(G\right),A\right)$ ，使得 $T\left(G\right)$ 不是 $\left(A,L,f\right)$ 可染的。容易得到G具有以下性质：

1) G的每一个顶点v至多与 $\lfloor \frac{d\left(v\right)}{2}\rfloor$ 个三角形相关联；

2) $\delta \ge 3$ ；

3) 若边 $uv\in E$ 且 $\min \left\{d\left(u\right),d\left(v\right)\right\}\le \frac{k}{2}$ ，则 $d\left(u\right)+d\left(v\right)\ge k+3$ 。

由于G不含相邻三角形，所以性质(1)显然成立。下面证明性质(2)和(3)。首先证明(2)，用反证法。假设v是G的一个2⁻-点且e是关联点v的一条边。令 $G^{\prime }=G-e$ 。根据G的极小性，得 $T\left(G^{\prime }\right)$ 有一个 $\left(A,L^{\prime },f^{\prime }\right)$ 染色c(其中 $L^{\prime }$ 为L在 $T\left(G^{\prime }\right)$ 上的限制， $f^{\prime }$ 为f在 $T\left(G^{\prime }\right)$ 上的限制)。c可看作是 $T\left(G\right)$ 的一个部分 $\left(A,L,f\right)$ 染色，欲将c拓展为 $T\left(G\right)$ 的 $\left(A,L,f\right)$ 染色。现擦除这个染色中点v的颜色，因而在 $T\left(G\right)$ 中只有顶点v和点e未染色。先对点e进行染色，设 $e_1,e_2,\cdots ,e_n,v$ 是e在 $T\left(G\right)$ 中的所有邻点。根据全图的定义和 $d\left(u\right)+d\left(v\right)\le k+2$ 有 $n=d_G\left(u\right)+d_G\left(v\right)-1\le k+1$ 。不失一般性，假设 $e{e}_i$ 的方向为由e指向 $e_i$ $\left(1\le i\le n\right)$，易得到 $\left|L\left(e\right)-{\displaystyle \underset{i=1}{\overset{n}{\cup }}\left\{c\left(e_i\right)+f\left(e{e}_i\right)\right\}}\right|\ge \left(k+2\right)-\left(k+1\right)=1$ ，因而至少有一种颜色可以对e进行染色。再对点v进行染色，设 $e,v_2,v_3,\cdots ,v_m$ 是v在 $T\left(G\right)$ 中的所有邻点。根据全图的定义和 $d\left(v\right)\le 2$ 有 $m=2d_G\left(v\right)\le 4$ ，则 $\left|L\left(v\right)-\left\{c\left(e\right)+f\left(ve\right)\right\}-{\displaystyle \underset{i=2}{\overset{m}{\cup }}\left\{c\left(v_i\right)+f\left(v{v}_i\right)\right\}}\right|\ge \left(k+2\right)-4>1$ ，所以至少有一种颜色可以对v进行染色。因此， $T\left(G^{\prime }\right)$ 的 $\left(A,L^{\prime },f^{\prime }\right)$ 染色可拓展到 $T\left(G\right)$ 的 $\left(A,L,f\right)$ 染色。这与 $T\left(G\right)$ 不是 $\left(A,L,f\right)$ 可染的矛盾，从而(2)成立。

其次证明性质(3)。用反证法。假设G中存在边 $e=uv$ 且 $\min \left\{d\left(u\right),d\left(v\right)\right\}\le \frac{k}{2}$ ，使得 $d\left(u\right)+d\left(v\right)\le k+2$ 。不妨设 $d\left(u\right)\le \frac{k}{2}$ 。令 $G^{\prime }=G-e$ 。根据G的极小性，得 $T\left(G^{\prime }\right)$ 有一个 $\left(A,L^{\prime },f^{\prime }\right)$ 染色c (其中 $L^{\prime }$ 为L在 $T\left(G^{\prime }\right)$ 上的限制， $f^{\prime }$ 为f在 $T\left(G^{\prime }\right)$ 上的限制)。c可看作是 $T\left(G\right)$ 的一个部分 $\left(A,L,f\right)$ 染色，欲将c拓展为 $T\left(G\right)$ 的 $\left(A,L,f\right)$ 染色。现擦除这个染色中点u的颜色，因而在 $T\left(G\right)$ 中只有顶点u和点e未染色。先对点e进行染色，假设 $e_1,e_2,\cdots ,e_n,u$ 是e在 $T\left(G\right)$ 中的所有邻点。那么根据全图的定义和 $d\left(u\right)+d\left(v\right)\le k+2$ ，有 $n=d_G\left(u\right)+d_G\left(v\right)-1\le k+1$ 。不失一般性，假设 $e{e}_i$ 的方向为由e指向 $e_i$ $\left(1\le i\le n\right)$，易得到 $\left|L\left(e\right)-{\displaystyle \underset{i=1}{\overset{n}{\cup }}\left\{c\left(e_i\right)+f\left(e{e}_i\right)\right\}}\right|\ge \left(k+2\right)-\left(k+1\right)=1$ ，因而至少有一种颜色可以对e进行染色。再对点u进行染色，设 $e,u_2,u_3,\cdots ,u_m$ 是u在 $T\left(G\right)$ 中的所有邻点。根据全图的定义和 $d\left(u\right)\le \frac{k}{2}$ 有 $m=2d_G\left(u\right)\le k$ ，则 $\left|L\left(u\right)-\left\{c\left(e\right)+f\left(ue\right)\right\}-{\displaystyle \underset{i=2}{\overset{m}{\cup }}\left\{c\left(u_i\right)+f\left(u{u}_i\right)\right\}}\right|\ge \left(k+2\right)-k>1$ ，所以至少有一种颜色可以对u进行染色。因此， $T\left(G^{\prime }\right)$ 的 $\left(A,L^{\prime },f^{\prime }\right)$ 染色可拓展到 $T\left(G\right)$ 的 $\left(A,L,f\right)$ 染色。这与 $T\left(G\right)$ 不是 $\left(A,L,f\right)$ 可染的矛盾，从而(3)成立。

由G是平面图可知欧拉公式 $\left|V\right|-\left|E\right|+\left|F\right|=2$ 成立。等式 $\left|V\right|-\left|E\right|+\left|F\right|=2$ 两端同时乘−6，得 $-6\left|V\right|+6\left|E\right|-6\left|F\right|=-12$ ，变形为：

${\displaystyle \underset{v\in V}{\sum }\left(d\left(v\right)-6\right)}+{\displaystyle \underset{f\in F}{\sum }\left(2d\left(f\right)-6\right)}=-12.$

对于任意 $x\in V\cup F$ ，定义x的初始权值：如果 $x\in V$ ，则 $ch\left(x\right)=d\left(x\right)-6$ ；如果 $x\in F$ ，则 $ch\left(x\right)=2d\left(x\right)-6$ 。那么有

${\displaystyle \underset{x\in V\cup F}{\sum }c}h\left(x\right)=-12<0.$

我们将利用权转移规则重新分配顶点和面的权值，用 $c{h}^{\prime }\left(x\right)$ 表示x的新的权值 $\left(x\in V\cup F\right)$ ，权转移规则如下：

R1 每个4⁺-面f向其关联的4⁻-点v转移 $m_v\left(f\right)$ ，向其关联的5-点v转移 $\frac{1}{3}{m}_v\left(f\right)$ 。

R2 若3-面f与3-点v关联，则f关联的另外两个点分别向v都转移 $\frac{1}{2}$ 。

下面计算点和面的新权值。首先考虑点的新权值。设 $d\left(v\right)=3$ ，根据性质(1)，v至多与1个3-面关联。若v只与1个3-面f关联，由权转移规则R2知，f所关联的另外两个点分别向v转移 $\frac{1}{2}$ ；由权转移规则R1知，v关联的两个4⁺-面分别向v转移1，故有 $c{h}^{\prime }\left(v\right)=ch\left(v\right)+2\times 1+2\times \frac{1}{2}=0$ ；若v不与3-面关联，由权转移规则R1知，v关联的每个面分别向v转移1，故 $c{h}^{\prime }\left(v\right)=ch\left(v\right)+3\times 1=0$ 。设 $d\left(v\right)=4$ ，根据性质(1)，v至多与2个3-面关联。由权转移规则R1得， $c{h}^{\prime }\left(v\right)\ge ch\left(v\right)+2\times 1=0$ 。设 $d\left(v\right)=5$ ，则v至多与2个3-面关联，由R1得 $c{h}^{\prime }\left(v\right)\ge ch\left(v\right)+3\times \frac{1}{3}=0$ 。设 $6\le d\left(v\right)\le 7$ ，由R1和R2知v既不转出权值，也不转入权值，故 $c{h}^{\prime }\left(v\right)=ch\left(v\right)\ge 0$ 。设 $d\left(v\right)\ge 8$ ，由v至多与 $\lfloor \frac{d\left(v\right)}{2}\rfloor$ 个3-面关联及R2得

$c{h}^{\prime }\left(v\right)\ge ch\left(v\right)-\frac{1}{2}\lfloor \frac{d\left(v\right)}{2}\rfloor \ge ch\left(v\right)-\frac{1}{2}\times \frac{d\left(v\right)}{2}=\frac{3}{4}d\left(v\right)-6\ge 0.$

其次考虑面的新权值。设 $d\left(f\right)=3$ ，由权转移规则知f既不转出权值，也不转入权值，故 $c{h}^{\prime }\left(f\right)=ch\left(f\right)=0$ 。设 $d\left(f\right)=4$ ，若f关联4⁻-点，由性质(3)知f至多关联2个4⁻-点，由R1得

$c{h}^{\prime }\left(f\right)\ge ch\left(f\right)-\max \left\{2\times 1,1+\frac{1}{3}\right\}=2d\left(f\right)-8=0$ ；若f不关联4⁻-点，由R1得 $c{h}^{\prime }\left(f\right)\ge ch\left(f\right)-\frac{1}{3}\times 4>0$ 。设 $d\left(f\right)\ge 5$ ，用n表示f关联的4⁻-点个数，由性质(3)知 $n\le \frac{d\left(f\right)}{2}$ ，根据权转移规则R1可得

$c{h}^{\prime }\left(f\right)\ge ch\left(f\right)-1\times n-\frac{1}{3}\left(d\left(f\right)-n\right)=\frac{5}{3}d\left(f\right)-\frac{2}{3}n-6\ge \frac{4}{3}d\left(f\right)-6>0.$

综上所述，对于 $\forall x\in V\cup F$ ，都有 $c{h}^{\prime }\left(x\right)\ge 0$ ，得到矛盾，从而完成了定理2.1的证明。

定理2.2设G是 $\Delta \le k$ ( $k\ge 6$ )的平面图，如果G中的3圈与3圈、4圈、5圈均不相邻，则 ${{\chi }^{″}}_{gl}\left(G\right)\le k+2$ 。

证明反证法。设G是满足定理2.2条件的 $\left|V\right|+\left|E\right|$ 最小的反例，则存在阿贝尔群A( $\left|A\right|\ge k+2$ )， $\left(k+2\right)$ 列表分配 $L:V\left(T\left(G\right)\right)\to 2^A$ 和 $f\in F\left(T\left(G\right),A\right)$ ，使得 $T\left(G\right)$ 不是 $\left(A,L,f\right)$ 可染的。类似于定理2.1的证明我们可以证明G具有以下性质：

1) G的每一个顶点v至多与 $\lfloor \frac{d\left(v\right)}{2}\rfloor$ 个三角形相关联；

2) $\delta \ge 3$ ；

3) 若边 $uv\in E$ 且 $\min \left\{d\left(u\right),d\left(v\right)\right\}\le \frac{k}{2}$ ，则 $d\left(u\right)+d\left(v\right)\ge k+3$ 。

由G是平面图可知欧拉公式 $\left|V\right|-\left|E\right|+\left|F\right|=2$ 成立。类似定理2.1的证明，可在 $\left|V\right|-\left|E\right|+\left|F\right|=2$ 的两端同乘−10，并变形为：

${\displaystyle \underset{v\in V}{\sum }\left(2d\left(v\right)-10\right)}+{\displaystyle \underset{f\in F}{\sum }\left(3d\left(f\right)-10\right)}=-20.$

对于任意 $x\in V\cup F$ ，定义x的初始权值：如果 $x\in V$ ，则 $ch\left(x\right)=2d\left(x\right)-10$ ；如果 $x\in F$ ，则 $ch\left(x\right)=3d\left(x\right)-10$ 。那么有

${\displaystyle \underset{x\in V\cup F}{\sum }ch\left(x\right)}=-20<0.$

我们将利用权转移规则重新分配顶点和面的权值，用 $c{h}^{\prime }\left(x\right)$ 表示x的新的权值 $\left(x\in V\cup F\right)$ ，权转移规则如下：

R1 每个6⁺-点向其相邻的3-点转移 $\frac{1}{3}$ 。

R2 每个4⁺-面f向其关联的3-点v转移 $m_v\left(f\right)$ ，向其关联的4-点v转移 $\frac{1}{2}{m}_v\left(f\right)$ 。

R3 每个6⁺-面f向其关联的3-点v转移 $\frac{3}{2}{m}_v\left(f\right)$ ，向其关联的4-点v转移 $m_v\left(f\right)$ 。

R4 每个6⁺-面f向其相邻的3-面转移 $\frac{1}{3}$ 。

下面计算点和面的新权值。首先考虑点的新权值。设 $d\left(v\right)=3$ ，根据性质(1)，v至多与1个3-面相关联。若v只与1个3-面f关联，由权转移规则R1知，每个6⁺-点向其相邻的3-点转移 $\frac{1}{3}$ ；由权转移规则R3知，v关联的两个6⁺-面分别向v转移 $\frac{3}{2}$ ，故有 $c{h}^{\prime }\left(v\right)=ch\left(v\right)+3\times \frac{1}{3}+2\times \frac{3}{2}=0$ ；若v不与3-面关联，由权转移规则R1知，每个6⁺-点向其相邻的3-点转移 $\frac{1}{3}$ ；由权转移规则R2知，v关联的每个面分别向v转移1，故有 $c{h}^{\prime }\left(v\right)=ch\left(v\right)+3\times \frac{1}{3}+3\times 1=0$ 。设 $d\left(v\right)=4$ ，根据性质(1)，点v至多与2个3-面相关联。若v与3-面f关联，由权转移规则R3知，v关联的两个6⁺-面分别向v转移1，故有 $c{h}^{\prime }\left(v\right)\ge ch\left(v\right)+2\times 1=0$ ；若v不与3-面关联，由权转移规则R2知，v关联的每个面分别向v转移 $\frac{1}{2}$ ，故 $c{h}^{\prime }\left(v\right)\ge ch\left(v\right)+4\times \frac{1}{2}=0$ 。设 $d\left(v\right)=5$ ，由权转移规则知v既不转出权值，也不转入权值，故 $c{h}^{\prime }\left(v\right)=ch\left(v\right)=0$ 。设 $d\left(v\right)\ge 6$ ，根据权转移规则R1知，每个6⁺-点向其相邻的3-点转移 $\frac{1}{3}$ ，可得

$c{h}^{\prime }\left(v\right)\ge ch\left(v\right)-\frac{1}{3}d\left(v\right)=\frac{5}{3}d\left(v\right)-10\ge 0.$

其次考虑面的新权值。设 $d\left(f\right)=3$ ，由条件可知面f与3个6⁺-面相邻，根据权转移规则R4知，每个6⁺-面f向其相邻的3-面转移 $\frac{1}{3}$ ，故 $c{h}^{\prime }\left(f\right)\ge ch\left(f\right)+3\times \frac{1}{3}=0$ 。设 $4\le d\left(f\right)\le 5$ ，若f关联3-点，根据权转移规则R2得 $c{h}^{\prime }\left(f\right)\ge ch\left(f\right)-2\times 1=3d\left(f\right)-10-2\ge 0$ ；若f不关联3-点，即面f关联的点均为4⁺-点，由R2得 $c{h}^{\prime }\left(f\right)\ge ch\left(f\right)-\frac{1}{2}\times d\left(f\right)=3d\left(f\right)-10-\frac{1}{2}d\left(f\right)=\frac{5}{2}d\left(f\right)-10\ge 0$ 。设 $d\left(f\right)\ge 6$ ，用n表示f关联的3-点的个数，由性质(3)知 $n\le \frac{d\left(f\right)}{2}$ ，根据权转移规则可得

$c{h}^{\prime }\left(f\right)\ge ch\left(f\right)-\frac{1}{3}d\left(f\right)-\frac{3}{2}n-\left(d\left(f\right)-2n\right)\ge \frac{5}{3}d\left(f\right)-10\ge 0.$

综上所述，对于 $\forall x\in V\cup F$ ，都有 $c{h}^{\prime }\left(x\right)\ge 0$ ，得到矛盾，从而完成定理2.2的证明。

3. 总结

本文给出了全群列表染色的结构性质，进一步揭示了全群列表染色可约构型的特点。利用结构性质，借助Discharging方法得到了两类不含相邻三角形的特殊平面图的全群选择数的上界，从而推进了平面图全群列表染色的研究。

基金项目

内蒙古自然科学基金项目(2022MS01007)；内蒙古自治区高等学校科学研究项目(NJZY22599, NJZY22600)；内蒙古师范大学基本科研业务费专项资金项目(2022JBTD007)。

NOTES

^*通讯作者。