稀疏图的适当无冲突列表着色的度可选性

《Discrete Mathematics》：Degree-choosability of proper conflict-free list coloring of sparse graphs

　　

摘要

给定一个图 G 和一个映射 f:V(G)→N，G 的 f-列表赋值是将每个 v∈V(G) 映射到一个至少包含 f(v) 个颜色的集合的函数。对于图 G 的 f-列表赋值 L，G 的正常无冲突 L-着色是 G 的一个正常着色 ?，使得对于 G 中每个非孤立顶点 v∈V(G)，有 ?(v)∈L(v)，且在 v 的邻域中恰好有某个颜色只出现一次。我们称 G 是正常无冲突 f-可选择的，如果对于 G 的任意 f-列表赋值 L，都存在 G 的正常无冲突 L-着色。如果 G 是正常无冲突 f-可选择的，且存在常数 k 使得对于 G 的每个顶点 v 有 f(v)=d_G(v)+k，则称 G 是正常无冲突 (度数+k)-可选择的。在本文中，我们研究最大平均度有界的图。我们证明：每个最大平均度小于 10/3 的图都是正常无冲突 (度数+3)-可选择的，且每个最大平均度小于 18/7 的图都是正常无冲突 (度数+2)-可选择的，除非它含有一个同构于 5-圈的连通分支。因此，每个圈长至少为 5 的平面图都是正常无冲突 (度数+3)-可选择的，每个圈长至少为 9 的平面图都是正常无冲突 (度数+2)-可选择的。

1. 引言

全文中，我们只考虑简单的、有限的、无向图。图 G 的 k-着色是一个映射 ?:V(G)→{1,2,…,k}。如果图的一个着色 ? 使得每个相邻顶点对获得不同的颜色，则称该着色 ? 是正常的。图 G 的色数，记为 χ(G)，是使 G 存在正常 k-着色的最小正整数 k。

对于图 G，如果一个着色 ? 是 G 的正常着色，且对于 G 中每个非孤立顶点 v∈V(G)，存在一种颜色在 v 的邻域中恰好出现一次，则称 ? 是正常无冲突的。图 G 的正常无冲突色数，记为 χ_pcf(G)，是使 G 存在正常无冲突 k-着色的最小正整数 k。图的正常无冲突着色的概念由 Fabrici、Lu?ar、Rindo?ová 和 Soták [4] 引入，他们研究了平面图和外平面图的正常无冲突着色。

对于图 G 和一个从 V(G) 到正整数的映射 f，G 的 f-列表赋值是一个每个顶点可用颜色的列表 L，使得对于每个 v∈V(G) 有 |L(v)|≥f(v)。对于 G 的列表赋值 L，G 的 L-着色是一个映射 ?:V(G)→?_{v∈V(G)} L(v)，使得对于每个 v∈V(G) 有 ?(v)∈L(v)。如果 G 对于 G 的任意 f-列表赋值 L 都有正常 L-着色，则称 G 是 f-可选择的。如果对于 V(G) 的每个顶点 v，G 在 f(v)=d_G(v) 时是 f-可选择的，则称 G 是度数可选择的。众所周知，连通图 G 不是度数可选择的当且仅当 G 是 Gallai 树，即 G 的每个块或者是完全图或者是一个奇圈。度数可选择图已在很多论文中被研究 [1]、[2]、[3]、[8]、[9]。

沿着这条路线，我们考虑正常无冲突着色的类比概念——度数可选择性。对于一个常数 k，G 的 (度数+k)-列表赋值是 f-列表赋值且 f(v)=d_G(v)+k。如果 G 对于 G 的任意 (度数+k)-列表赋值 L 都是正常无冲突 L-可着色的，则称 G 是正常无冲突 (度数+k)-可选择的。我们在 [7] 中提出的一个基本问题是：是否存在一个绝对常数 k 使得每个图都是正常无冲突 (度数+k)-可选择的。当 k 较小时，我们知道 C? 不是正常无冲突 (度数+2)-可选择的，且存在无穷多个图不是正常无冲突 (度数+1)-可选择的。（见 [5] 中的命题 4。）考虑到这些例子，我们提出以下猜想。

猜想 1.1 [5] 每个连通图，除 5-圈 C? 外，都是正常无冲突 (度数+2)-可选择的。

猜想 1.2 每个最小度至少为 3 的连通图都是正常无冲突 (度数+1)-可选择的。

猜想 1.1 对于一些图类已经被验证，例如至多三次图 [7]、外平面图 [5]、无 K?-子式的最大度至多为 4 的图 [10]，以及最大度至多为 4 的外 1-平面图 [10]。尽管完全解决猜想 1.1、猜想 1.2 似乎很有难度，但以下观察可以很容易地证明出来（见 [6] 中的证明）。

观察 1.3 如果图 G 是 d-退化的（d 为某个正整数），则 G 是正常无冲突 (度数+d+1)-可选择的。

上述界只是一个观察，但我们发现将其减少 1 可能是相当有挑战性的。我们相信该结论成立，唯一的例外是 5-圈 C?，如下所述。

猜想 1.4 [6] 如果连通图 G≠C? 是 d-退化的（d 为某个正整数），则 G 是正常无冲突 (度数+d)-可选择的。

猜想 1.4 对于 d=1 [6] 和一些特殊图族已经被验证。例如，众所周知平面图是 5-退化的，外平面图是 2-退化的。我们证明了除 C? 外，每个连通外平面图都是正常无冲突 (度数+2)-可选择的 [5]。此外，我们证明每个平面图都是正常无冲突 (度数+5)-可选择的，这将发表在一篇单独的论文中。

在本文中，我们研究最大平均度有界的图。对于图 G，其最大平均度，记为 mad(G)，是 2|E(H)|/|V(H)| 在所有 G 的子图 H 中取到的最大值。最大平均度是衡量图稀疏性的一个参数，因此关于最大平均度有界的图的着色有很多结果。我们的主要结果如下，我们分别在第 2 节和第 3 节中给出定理 1.5 和定理 1.6 的证明。

定理 1.5 每个 mad(G)<10/3 的图 G 都是正常无冲突 (度数+3)-可选择的。

定理 1.6 每个 mad(G)<18/7 的图 G 都是正常无冲突 (度数+2)-可选择的，除非它含有一个同构于 C? 的连通分支。

如果一个图 H 的平均度至多为 10/3<4，则容易看出 H 有一个度至多为 3 的顶点。因此，mad(G)<10/3 的假设意味着 G 是 3-退化的。类似地，每个 mad(G)<18/7 的图 G 是 2-退化的。因此，定理 1.5 和定理 1.6 支持了猜想 1.4。

此外，以下是我们主要结果的直接推论和 Euler 公式的推论。

推论 1.7 设 G 为一个平面图。
- 如果 G 的圈长至少为 5，则 G 是正常无冲突 (度数+3)-可选择的。
- 如果 G 的圈长至少为 9，则 G 是正常无冲突 (度数+2)-可选择的。

后者改进了 Wang 和 Zhang [10] 最近结果中的圈长条件，他们证明了每个圈长至少为 12 的平面图都是正常无冲突 (度数+2)-可选择的。

我们以介绍本文使用的记号来结束这一节。对于图 G 的子图 H 和顶点 v∈V(G)（不一定在 H 中），我们用 N_H(v) 表示 v 在 V(H) 中的邻居。对于集合 S?V(G)，我们用 N_H(S) 表示 V(H) 中所有在 S 中有邻居的顶点。对于 G 的（部分）着色 ? 和子集 R?V(G)，令 ?(R) 为 ? 在 R 上所有已用颜色的集合（R 中的每个顶点不一定在 ? 中被着色）。对于 G 的（部分）正常无冲突着色 ?，令 U_?(v,G) 为在 G 中 v 的邻域中恰好出现一次的颜色集合。对于图 G 中的顶点 u，我们说 u 是 G 中的 k-顶点（k?-顶点、k?-顶点）如果 d_G(u)=k（d_G(u)≥k、d_G(u)≤k）。与顶点 u 相邻的 k-顶点（k?-顶点、k?-顶点）称为 u 的 k-邻居（k?-邻居、k?-邻居）。

2. 定理 1.5 的证明

假设结论不成立，令 G 为一个反例，使得 |V(G)|+|E(G)| 尽可能小。假设 L 是 G 的一个 (度数+3)-列表赋值，使得 G 不是正常无冲突 L-可着色的。

2.1 禁止构型

我们给出 G 的一些禁止构型的命题。容易看出，具有至少三种可用颜色的 1-顶点是可约的，因此我们可以假设 δ(G)≥2。

命题 2.1 2-顶点不包含在三角形中。

证明：假设 G 有一个包含在三角形 uv?v? 中的 2-顶点 u。令 G′=G?u。由 G 的最小性，G′ 存在正常无冲突 L-着色 ?。由于 δ(G)≥2，{v?,v?} 中的任何顶点都不是 G′ 的孤立顶点，因此对于每个 i∈{1,2}，我们选择 c_{v_i}∈U_?(v_i,G′)。我们通过选择 ?(u)∈L(u)?{?(v?),?(v?),c_{v_1},c_{v_2}} 将 ? 扩展到 u。由于 ?(v?)≠?(v?)，我们有 ?(v?)∈U_?(u,G)，因此 ? 是 G 的正常无冲突 L-着色，矛盾。□

命题 2.2 如果 u 和 v 都是 2-顶点，则 N_G(u)≠N_G(v)。

证明：假设 G 有两个 2-顶点 u 和 v 使得 N_G(u)=N_G(v)={w?,w?}。令 G′=G?u。由 G 的最小性，G′ 存在正常无冲突 L-着色 ?。使用与命题 2.1 证明中类似的论证，我们可以将 ? 扩展为 G 的正常 L-着色，使得对于任何 w∈V(G)?{u} 有 U_?(w,G)≠?。此外，由于 U_?(v,G)≠?，我们知道 ?(w?)≠?(w?)。因此，U_?(u,G)≠?，且 ? 是 G 的正常无冲突 L-着色，矛盾。□

命题 2.3 3?-顶点不相邻于另一个 3?-顶点。

证明：反设 G 有两个相邻的 3?-顶点 u 和 v。令 d_G(u)=k+1 且 d_G(v)=?+1，其中 k,?∈{1,2}。令 u?,u?,…,u_k 为 u 不同于 v 的邻居，令 v?,v?,…,v_? 为 v 不同于 u 的邻居。令 G′=G?{u,v}。由 G 的最小性，G′ 存在正常无冲突 L-着色 ?。由命题 2.1，u 和 v 没有公共的 2-邻居，因此 G′ 没有孤立顶点。对于每个 w∈N_{G′}(u)∪N_{G′}(v)，我们选择一个颜色 c_w∈U_?(w,G′)。令

L*(u)=L(u)?(?(N_{G′}(u))∪{c_w | w∈N_{G′}(u)})
L*(v)=L(v)?(?(N_{G′}(v))∪{c_w | w∈N_{G′}(v)})

回忆 ?(N_{G′}(u))={?(x) | x∈N_{G′}(u)}。显然，|L*(u)|≥k+4?2k≥2 且 |L*(v)|≥?+4?2?≥2。我们将 ? 扩展为 G 的正常无冲突 L-着色。

如果 |L*(u)|=2，则必有 d_G(u)=3 且 ?(u?)≠?(u?)。因此，我们可以选择 ?(u)∈L*(u)?{?(v?)}，然后选择 ?(v)∈L*(v)?{?(u)}。显然 ? 是正常的。由于 d_G(u)≤3 且 d_G(v)≤3，?(u)≠?(v?) 保证 U_?(v,G)≠?，而 ?(u?)≠?(u?) 保证 U_?(u,G)≠?。因此，? 是 G 的正常无冲突 L-着色，矛盾。

因此，我们可以假设 |L*(u)|≥3。然后我们选择 ?(v)∈L*(v)?{?(u?)}，随后选择 ?(u)∈L*(u)?{?(v),?(v?)}。通过与前一段类似的论证，? 是 G 的正常无冲突 L-着色。□

命题 2.4 对于任意整数 k≥4，G 的每个 k-顶点至多有 (k?3) 个 2-邻居。

证明：反设 u∈V(G)，其中 N_G(u)={u?,u?,…,u_k}，其中 u?,u?,…,u_{k?2} 的度为 2。对于每个 i∈{1,2,…,k?2}，令 v_i 为 u_i 除 u 外的邻居。令 G′=G?{u,u?,u?,…,u_{k?2}}。由 G 的最小性，G′ 存在正常无冲突 L-着色 ?。由命题 2.1 和命题 2.2，u_{k?1},u_k,v?,v?,…,v_{k?2} 是 G 中两两不同的顶点，因此它们都不是 G′ 的孤立顶点。对于每个 w∈{u_{k?1},u_k,v?,v?,…,v_{k?2}}，选择一个颜色 c_w∈U_?(w,G′)。我们定义列表赋值 L* 为：

- L*(u)=L(u)?(?({u_{k?1},u_k,v?,v?,…,v_{k?2}})∪{c_{u_{k?1}},c_{u_k}})
- 对于每个 i∈{1,2,…,k?2}，令 L*(u_i)=L(u_i)?{?(v_i),c_{v_i}}

显然，我们有 |L*(u)|≥k+3?k?2=1 且 |L*(u_i)|≥5?2=3。

现在，我们将 ? 扩展为 G 的正常无冲突 L-着色。我们首先任意选择 ?(u)∈L*(u)。如果 ?(u_{k?1})=?(u_k)，则我们选择 ?(u?)∈L*(u?)?{?(u),?(u_k)}，且对于每个 i∈{2,3,…,k?2}，令 ?(u_i)∈L*(u_i)?{?(u),?(u?)}。否则，对于每个 i∈{1,2,…,k?2}，选择 ?(u_i)∈L*(u_i)?{?(u),?(u_k)}。在任何一种情况下，容易看出 ? 是一个正常的 L-着色，使得对于 V(G)?{u} 中的每个顶点 w 都有 U_?(w,G)≠?。由 ?(u?),?(u?),…,?(u_{k?2}) 的选择，当 ?(u_{k?1})=?(u_k) 时 ?(u?)∈U_?(u,G)，当 ?(u_{k?1})≠?(u_k) 时 ?(u_k)∈U_?(u,G)，因此 ? 是 G 的正常无冲突 L-着色，矛盾。□

命题 2.5 对于任意整数 k≥4，如果一个 k-顶点 u 有 (k?3) 个 2-邻居，则 u 没有 3-邻居。

证明：令 u∈V(G) 为一个 k-顶点（k≥4），其中 N_G(u)={u?,u?,…,u_k}。反设 d_G(u?)=d_G(u?)=?=d_G(u_{k?3})=2 且 d_G(u_{k?2})=3。对于每个 i∈{1,2,…,k?3}，令 v_i 为 u_i 除 u 外的邻居。令 G′=G?{u,u?,u?,…,u_{k?3}}。由 G 的最小性，图 G′ 存在正常无冲突 L-着色 ?。由命题 2.1 和命题 2.2，u_{k?2},u_{k?1},u_k,v?,v?,…,v_{k?3} 是 G 中两两不同的顶点，因此它们都不是 G′ 的孤立顶点。对于每个 w∈{u_{k?1},u_k,v?,v?,…,v_{k?3}}，选择一个颜色 c_w∈U_?(w,G′)。

我们定义列表赋值 L* 为：

- L*(u)=L(u)?(?({u_{k?2},u_{k?1},u_k,v?,v?,…,v_{k?3}})∪{c_{u_{k?1}},c_{u_k}})
- 对于每个 i∈{1,2,…,k?3}，L*(u_i)=L(u_i)?{?(v_i),c_{v_i}}

显然，我们有 |L*(u)|≥1 且 |L*(u_i)|≥3。

现在，我们将 ? 扩展为 G 的正常无冲突 L-着色。首先，任意选择 ?(u)∈L*(u)。注意无论我们为 ?(u) 分配什么颜色，U_?(u_{k?2},G)≠? 都成立，因为 d_G(u_{k?2})=3 且在 N_G(u_{k?2})?{u} 中出现了两种不同的颜色。

既然 u 在此时有三个着色邻居 {u_{k-2}, u_{k-1}, u_k}，要么它们都被着上同一种颜色 α，要么恰好有一种颜色 β 只出现在其中某一个上。在前一种情况下，令 ?(u_1) ∈ L*(u_1) \ {?(u), α}，并对每个 i ∈ {2, 3, …, k-3}，选取 ?(u_i) ∈ L*(u_i) \ {?(u), ?(u_1)}。在后一种情况下，对每个 i ∈ {1, 2, …, k-3}，选取 ?(u_i) ∈ L*(u_i) \ {?(u), β}。容易验证 ? 是一个正规的 L-着色，且对每个 w ∈ V(G) \ {u}，U_?(w, G) ≠ ?。此外，由于在前一种情况下 ?(u_1) ∈ U_?(u, G)，在后一种情况下 β ∈ U_?(u, G)，所以 ? 是 G 的一个正规冲突自由 L-着色，矛盾。

**2.2 移法**

对每个 v ∈ V(G)，定义初始电荷为 c(v) = 3d_G(v) - 10。

我们应用以下移法规则：
- 每个 4+ 顶点向每个相邻的 2-顶点发送电荷 2。
- 每个 4+ 顶点向每个相邻的 3-顶点发送电荷 1/3。

我们将证明在应用移法规则后，对所有 v ∈ V(G)，最终电荷 c*(v) ≥ 0。如果 v 是一个 3-顶点，则由断言 2.3 和移法规则显然有 c*(v) = 0。

设 v 是一个 k-顶点，k ≥ 4。对每个正整数 k，令 n_k 表示 v 的 k-邻居的数量。由断言 2.4，n_2 ≤ k - 3。

如果 n_2 = k - 3，则由断言 2.5 得 n_3 = 0，因此
c*(v) = c(v) - 2n_2 - (1/3)n_3 = c(v) - 2(k-3) = 3k - 10 - 2(k-3) = k - 4 ≥ 0。

否则，由于 n_2 ≤ k - 4 且 n_2 + n_3 ≤ k，有
c*(v) = c(v) - 2n_2 - (1/3)n_3 ≥ c(v) - 2(k-4) - (1/3)·4 = 3k - 10 - 2k + 8 - 4/3 = (k - 10)/3 > 0。

因此，在移法之后，V(G) 中的每个元素都具有非负电荷，从而
0 ≤ Σ_{v∈V(G)} c*(v) = Σ_{v∈V(G)} c(v) = Σ_{v∈V(G)} (3d_G(v) - 10) = 6|E(G)| - 10|V(G)|。

然而，这意味着 mad(G) ≥ 2|E(G)|/|V(G)| ≥ 10/3，矛盾。这完成了定理 1.5 的证明。

**3. 定理 1.6 的证明**

假设结论不成立，令 G 为一个反例，使得 |V(G)| + |E(G)| 尽可能小。假设 L 是 G 的一个 (degree+2)-列表赋值，使得 G 不是正规冲突自由 L-可着色的。由于每个长度 ? ≠ 5 的圈都是正规冲突自由 4-可选的，所以 G 不是一个圈。

G 的一个 k-链是指 G 中一个包含 k 个顶点的路径，其中每个顶点在 G 中度为 2。注意，如果一个图包含一个 k-链，则对于任何 1 ≤ ? ≤ k-1，它也包含一个 ?-链。如果一个 k-链不包含在其作为子图的 (k+1)-链中，则称该 k-链为极大的。对于顶点 u，我们说 u 与一个 k-链关联，如果存在一条路径 uv_1v_2?v_k，其中 v_1v_2?v_k 是一个 k-链。注意，一个 1-链就是一个 2-顶点。

在我们开始分析最小反例的结构之前，我们先给出关于某些指定图形的正规冲突自由 (degree+2)-可选性的一些命题。

**3.1 辅助结果**

**命题 3.1** [5] 令 C = v_0v_1v_2v_3v_4v_0 为一个 5-圈。假设 L 是 C 的一个 4-列表赋值。则 C 不是正规冲突自由 L-可着色的，当且仅当 L(v_0) = L(v_1) = L(v_2) = L(v_3) = L(v_4) 且 |L(v_0)| = 4。

**命题 3.2** 对正整数 r，完全二分图 K_{2,r} 是正规冲突自由 (degree+2)-可选的。

*证明* 设 {x, y} 和 {u_1, u_2, …, u_r} 为 K_{2,r} 的两个部分，令 L 为 K_{2,r} 的一个 (degree+2)-列表赋值。我们先选取三种不同的颜色 ?(x) ∈ L(x)，?(y) ∈ L(y)，以及 ?(u_1) ∈ L(u_1)。对 i ∈ {2, 3, …, r}，由于 |L(u_i)| ≥ 4，令 ?(u_i) ∈ L(u_i) \ {?(x), ?(y), ?(u_1)}。由颜色的选取，我们有 ?(u_1) ∈ U_?(x, K_{2,r})，?(u_1) ∈ U_?(y, K_{2,r})，以及 ?(x) ∈ U_?(u_i, K_{2,r})，从而 ? 是 K_{2,r} 的一个正规冲突自由 L-着色。

对于非负整数三元组 (r, s, t)，令 Θ_{1, 2^*, r, 3^*, s, 4^*, t} 为一个由两个度为 r+s+t+1 的顶点 x 和 y，以及 r+s+t+1 条内部不相交的路径 P_0, P_1, …, P_{r+s+t} 连接 x 和 y 组成的图，其中 |E(P_0)| = 1，对 1 ≤ i ≤ r，|E(P_i)| = 2，对 r+1 ≤ i ≤ r+s，|E(P_i)| = 3，对 r+s+1 ≤ i ≤ r+s+t，|E(P_i)| = 4。

**命题 3.3** 令 (r, s, t) 为满足 r+s ≥ 1 且 r+s+t ≥ 2 的非负整数三元组。则 Θ_{1, 2^*, r, 3^*, s, 4^*, t} 是正规冲突自由 (degree+2)-可选的。

*证明* 我们固定满足 r+s ≥ 1 且 r+s+t ≥ 2 的非负整数三元组 (r, s, t)。令 x 和 y 为两个相邻的度为 r+s+t+1 的顶点，令 P_1, P_2, …, P_{r+s+t} 为内部不相交的路径连接 x 和 y，其中
P_i = {xu_iy}（如果 1 ≤ i ≤ r），
P_i = {xu_iv_iy}（如果 r+1 ≤ i ≤ r+s），
P_i = {xu_iv_iw_iy}（如果 r+s+1 ≤ i ≤ r+s+t）。

令 L 为 Θ_{1, 2^*, r, 3^*, s, 4^*, t} 的一个 (degree+2)-列表赋值。通过删除多余的颜色，我们可以假设 |L(x)| = |L(y)| = r+s+t+3 且 |L(u_i)| = |L(v_i)| = |L(w_i)| = 4 对每个 i ∈ {1, 2, …, r+s+t}。

令 C := {{α, β} | α ≠ β, α ∈ L(x), β ∈ L(y)}。由于 |L(x)| = |L(y)| = r+s+t+3，我们有 |C| ≥ C(r+s+t+3, 2)。

对每个颜色对 {α, β} ∈ C，令
I_{α,β} := {i | r+s+1 ≤ i ≤ r+s+t, {α, β} ? L(v_i)}。

由于对每个 i ∈ {r+s+1, r+s+2, …, r+s+t}，|L(v_i)| = 4，在 C 中至多有 C(4,2) = 6 个不同的颜色对被包含在 L(v_i) 中。由假设 r+s ≥ 1 和 r+s+t ≥ 2，我们有
Σ_{{α,β}∈C} |I_{α,β}| ≤ Σ_{i=r+s+1}^{r+s+t} C(|L(v_i)|, 2) = 6t < C(r+s+t+3, 2) ≤ |C|，

这意味着存在一个对 {α, β} ∈ C 使得 I_{α,β} = ?。不失一般性，我们可以假设 α ∈ L(x) 且 β ∈ L(y)。令 ?(x) = α 且 ?(y) = β。对其他顶点，我们选择颜色如下：
- 对每个 i ∈ {1, 2, …, r}，令 ?(u_i) ∈ L(u_i) \ {α, β}。
- 对每个 i ∈ {r+1, r+2, …, r+s}，令 ?(u_i) ∈ L(u_i) \ {α, β} 且 ?(v_i) ∈ L(v_i) \ {α, β, ?(u_i)}。
- 对每个 i ∈ {r+s+1, r+s+2, …, r+s+t}，令 ?(u_i) ∈ L(u_i) \ {α, β}，?(w_i) ∈ L(w_i) \ {α, β, ?(u_i)}，且 ?(v_i) ∈ L(v_i) \ {α, β, ?(u_i), ?(w_i)}，其中 ?(v_i) 可以被选取是因为 |L(v_i) ∩ {α, β}| ≤ 1。

然后我们有 β ∈ U_?(x, Θ_{1,2^*,r,3^*,s,4^*,t}) 且 α ∈ U_?(y, Θ_{1,2^*,r,3^*,s,4^*,t})，且容易验证 ? 是一个正规冲突自由 L-着色。

**3.2 禁止构型**

在以下断言中，我们给出最小反例 G 的一些禁止构型。显然，度为 1 的顶点是可约化的，因此我们可以假设 δ(G) ≥ 2。

**断言 3.1** 一个 3-顶点不与 G 的 2-链关联。

*证明* 假设一个 3-顶点 u 与一个 2-链 v_1v_2 关联，且 uv_1 ∈ E(G)。令 v 为 v_2 的不同于 v_1 的邻居。注意对 i ∈ {1, 2}，|L(v_i)| ≥ 4。令 G' = G - {v_1, v_2}。则 G' 是正规冲突自由 L-可着色的；如果 G' 有一个与 C_5 同构的分量，则由命题 3.1 和 G' 的每个分量有一个顶点 x 满足 |L(x)| ≥ d_G(x) + 2 ≥ d_{G'}(x) + 3 可知这一点，否则由 G 的最小性可知这一点。令 ? 为 G' 的一个正规冲突自由 L-着色。由于 d_{G'}(v) ≥ δ(G) - 1 ≥ 1，我们选取 c_v ∈ U_?(v, G')。我们通过选择 ?(v_2) ∈ L(v_2) \ {?(u), ?(v), c_v} 以及 ?(v_1) ∈ L(v_1) \ {?(v_2), ?(u), ?(v)} 将 ? 扩展为 G 的一个 L-着色。由于 d_G(u) = 3 且 u 的邻居中至少出现两种颜色，? 是 G 的一个正规冲突自由 L-着色，矛盾。

**断言 3.2** G 没有 4-链。

*证明* 假设 P = v_1v_2v_3v_4 是一个 4-链，其中 u 是 v_1 的不同于 v_2 的邻居，v 是 v_4 的不同于 v_3 的邻居。令 G' = G - V(P)。由命题 3.1 和 G 的最小性，图 G' 有一个正规冲突自由 L-着色 ?。对每个 w ∈ {u, v}，选取一种颜色 c_w ∈ U_?(w, G')。令 L*(v_1) = L(v_1) \ {c_u, ?(u)}，L*(v_2) = L(v_2) \ {?(u)}，L*(v_3) = L(v_3) \ {?(v)}，L*(v_4) = L(v_4) \ {c_v, ?(v)}。注意对 i ∈ {1, 4}，|L*(v_i)| ≥ 2，对 j ∈ {2, 3}，|L*(v_j)| ≥ 3。我们可以通过从列表中删除多余的颜色假设 |L*(v_1)| = 2。然后我们如下将 ? 扩展为 G 的一个着色：首先，选取 ?(v_2) ∈ L*(v_2) \ L*(v_1)；然后选取 ?(v_4) ∈ L*(v_4) \ {?(v_2)}；接下来选取 ?(v_3) ∈ L*(v_3) \ {?(v_2), ?(v_4)}；最后，选取 ?(v_1) ∈ L*(v_1) \ {?(v_3)}。由这些选择显然 ? 是正规的。我们有对每个 w ∈ {u, v}，c_w ∈ U_?(w, G)，且每个 v_i 的两个邻居在 ? 中获得了两种不同的颜色。因此 ? 是 G 的一个正规冲突自由着色，矛盾。

**断言 3.3** G 没有圈 u_1u_2?u_?u_1 满足 d_G(u_2) = ? = d_G(u_?) = 2。

*证明* 假设 G 有一个圈 u_1u_2?u_?u_1 满足 d_G(u_2) = ? = d_G(u_?) = 2。由于由断言 3.2 知 G 没有 4-链，我们知道 ? ∈ {3, 4}。

令 G' = G - {u_2, u_3, …, u_?}。由命题 3.1 和 G 的最小性，G' 有一个正规冲突自由 L-着色 ?。由于 G 不是一个圈，我们有 d_{G'}(u_1) = d_G(u_1) - 2 ≥ 1，因此令 c_{u_1} 为 U_?(u_1, G') 中的一种颜色。

如果 ? = 3，则令 ?(u_2) ∈ L(u_2) \ {?(u_1), c_{u_1}} 且 ?(u_3) ∈ L(u_3) \ {?(u_1), ?(u_2), c_{u_1}}。如果 ? = 4，则令 ?(u_2) ∈ L(u_2) \ {?(u_1), c_{u_1}}，?(u_4) ∈ L(u_4) \ {?(u_1), ?(u_2), c_{u_1}}，以及 ?(u_3) ∈ L(u_3) \ {?(u_1), ?(u_2), ?(u_4)}。对于每种情况，容易验证着色 ? 是 G 的一个正规冲突自由 L-着色，矛盾。

**断言 3.4** 每个 3+ 顶点与至少一个 3+ 顶点相邻。

*证明* 假设存在一个 k-顶点（k ≥ 3）u_0 ∈ V(G)，N_G(u_0) = {u_1, u_2, …, u_k}，使得 d_G(u_i) = 2 对每个 i ∈ {1, 2, …, k}。我们固定这样的顶点 u_0 使得度 k 尽可能小。通过删除多余的颜色，我们可以假设 |L(u_i)| = 4 对每个 i。对每种颜色 c ∈ L(u_0)，令 U_c = {u_i | c ∈ L(u_i), 1 ≤ i ≤ k}。我们首先声称存在一种颜色 α ∈ L(u_0) 使得 |U_α| ≤ min{3, k-1}。事实上，如果 k = 3，则我们可以选取一种颜色 α ∈ L(u_0) \ L(u_1)，满足 U_α ? {u_2, u_3}。如果 k ≥ 4，则由于 Σ_{c∈L(u_0)} |U_c| ≤ Σ_{i=1}^k |L(u_i)| = 4k，存在一种颜色 α 使得 |U_α| ≤ ?4k/|L(u_0)|? ≤ ?4k/(k+2)? ≤ 3，如所需。不失一般性，我们可以假设 u_1 ? U_α。

令 v_i 为 u_i 的不同于 u_0 的邻居。由断言 3.3，我们知道对任何不同的 i 和 j，v_i ≠ u_j。注意对不同的 i 和 j，v_i = v_j 是有可能的。令 G' = G - {u_0, u_1, …, u_k}。如果 G' 有一个孤立顶点 v，则必有 N_G(v) ? {u_1, u_2, …, u_k}。由 k 的最小性，我们有 N_G(v) = {u_1, u_2, …, u_k}。这意味着 G 是一个完全二分图，两部分为 {u_0, v} 和 {u_1, u_2, …, u_k}，且由命题 3.2，G 是正规冲突自由 L-可着色的，矛盾。

因此 G' 没有孤立顶点。令 L' 为 G' 的一个列表赋值，使得对每个 i ∈ {1, 2, …, k}，L'(v_i) = L(v_i) \ {α}，且对每个顶点 x ∈ V(G') \ {v_1, v_2, …, v_k}，L'(x) = L(x)。则对每个顶点 v ∈ V(G')，|L'(v)| ≥ d_{G'}(v) + 2。特别地，如果顶点 v ∈ V(G') 与 {u_1, u_2, …, u_k} 中至少两个顶点相邻，则我们有 |L'(v)| ≥ |L(v)| - 1 ≥ d_G(v) + 2 - 1 ≥ d_{G'}(v) + 3。我们说 G' 的一个分量 H 是坏的，如果 H 与 C_5 同构且对每个顶点 v ∈ V(H)，|L'(v)| = 4。注意坏分量 H 的每个顶点至多与 {u_1, u_2, …, u_k} 中的一个顶点相邻，因此 H 的每个顶点在 G 中度为 2 或 3。

现在我们定义一个正规 L'-着色 ? 和对每个 i ∈ {1, 2, …, k} 的颜色 c_i 如下：
(a) 如果 G' 是正规冲突自由 L'-可着色的，则令 ? 为 G' 的一个正规冲突自由 L'-着色，且对每个 i ∈ {1, 2, …, k}，令 c_i 为 U_?(v_i, G') 中的一种颜色。
(b) 否则，G' 有一个坏分量。对 G' 的每个坏分量 H，我们令 ? 为 H 的一个正规 L'-着色，使得至多一个顶点 v_H 满足 U_?(v_H, G') = ?。对其他分量，令 ? 为正规冲突自由 L'-着色。

对每个 i ∈ {1, 2, …, k}，如果 U_?(v_i, G') ≠ ?，则令 c_i 为 U_?(v_i, G') 中的一种颜色。如果 U_?(v_i, G') = ?，则 v_i = v_H 对于某个坏分量 H，且 d_{G'}(v_H) = 2。因此令 c_i 为 ? 在 N_{G'}(v_i) 中出现的唯一颜色。

我们将 ? 扩展为 G 的一个正规冲突自由 L-着色。令 ?(u_0) = α，并对每个 u_i ∈ U_α 任意选取 ?(u_i) ∈ L(u_i) \ {?(v_i), c_i, α}。我们定义一种颜色 β 如下：如果 U_α = ?，则令 β 为 L(u_1) \ {?(v_1), c_1, α} 中的一种颜色，并令 ?(u_1) = β。如果 U_α ≠ ? 且 |?(U_α)| = 1，则由于 α ? L(u_1)，令 β 为 L(u_1) \ ({?(v_1), c_1, α} ∪ ?(U_α)) 中的一种颜色，并令 ?(u_1) = β。否则 U_α ≠ ? 且 |?(U_α)| ≥ 2，由 |U_α| ≤ 3 可知某种颜色在 U_α 中恰好出现一次，令 β 为该颜色。最后，对每个未着色的顶点 u_j，由于 u_j ? U_α，我们可以选取一种颜色 ?(u_j) ∈ L(u_j) \ {?(v_j), c_j, α, β}。

容易验证 ? 是 G 的一个正规 L-着色，且对每个 w ∈ V(G') \ {v_1, v_2, …, v_k}，U_?(w, G) = U_?(w, G') ≠ ?。由于 ?(u_i) ≠ c_i，当 c_i ∈ U_?(v_i, G') 时，我们有 c_i ∈ U_?(v_i, G)；当 U_?(v_i, G') = ? 时，我们有 ?(u_i) ∈ U_?(v_i, G)。由 L' 的定义，我们有 ?(v_i) ≠ α = ?(u_0)，因此 α ∈ U_?(u_i, G) 对每个 i ∈ {1, 2, …, k}。此外，由颜色 {?(u_i) | 1 ≤ i ≤ k} 的选取，我们有 β ∈ U_?(u_0, G)。因此 ? 是 G 的一个正规冲突自由 L-着色，矛盾。

**断言 3.5** 对任何 k ≥ 4，每个 k-顶点至多与 k-3 条 3-链关联。

*证明* 令 u_0 为具有邻居 u_1, u_2, …, u_k 的 k-顶点，k ≥ 4。假设 u_1, u_2, …, u_{k-2} 中每个都包含在 G 的一个 3-链中。我们固定这样的顶点 u_0 使得度 k 尽可能小。对每个 i ∈ {1, 2, …, k-2}，令 u_i v_i w_i 为一个包含 u_i 的 3-链，且 x_i 为 w_i 的不同于 v_i 的邻居。由断言 3.3，注意对任何不同的 i 和 j，{u_i, v_i, w_i, x_i} ∩ {u_j, v_j, w_j} = ?。令 G' = G - {u_0} ∪ ?_{i=1}^{k-2} {u_i, v_i, w_i}。如果 G' 有一个孤立顶点 v，则必有 N_G(v) ? {u_0, w_1, w_2, …, w_{k-2}}，从而 v 是一个度至多为 k-1 且与至少 d_G(v)-1 条 3-链关联的顶点，由 k 的最小性矛盾。

因此 G' 没有孤立顶点。由命题 3.1 和 G 的最小性，G' 有一个正规冲突自由 L-着色 ?。对每个 v ∈ {u_{k-1}, u_k, x_1, x_2, …, x_{k-2}}，令 c_v 为 U_?(v, G') 中的一种颜色。我们定义剩余顶点的列表赋值 L* 如下：
- 令 L*(u_0) = L(u_0) \ {?(u_{k-1}), ?(u_k), c_{u_{k-1}}, c_{u_k}}。
- 对每个 i ∈ {1, 2, …, k-2}，令 L*(u_i) = L(u_i)，L*(v_i) = L(v_i) \ {?(x_i)}，L*(w_i) = L(w_i) \ {?(x_i), c_{x_i}}。

通过删除多余的颜色，我们可以假设 |L*(u_i)| = 4，|L*(v_i)| = 3，|L*(w_i)| = 2 对每个 i ∈ {1, 2, …, k-2}。对每个 i ∈ {1, 2, …, k-2}，令 C(u_i) 为 L*(u_i) \ L*(w_i) 中的一个由两种颜色组成的集合。我们将证明可以将 ? 正规地扩展到 {u_0, u_1, …, u_{k-2}}，使得 U_?(u_0, G) ≠ ? 且 ?(u_i) ∈ C(u_i) 对每个 i ∈ {1, 2, …, k-2}。

情形 1. ?(u_{k-1}) = ?(u_k)。

令 α = ?(u_{k-1}) = ?(u_k)。我们首先选取 ?(u_1) ∈ C(u_1) \ {α}，并对每个 i ∈ {2, 3, …, k-2}，选取 ?(u_i) ∈ C(u_i) \ {?(u_1)}。由本情形的假设，我们有 |L*(u_0)| ≥ k+2-3 = k-1，因此我们可以选取 ?(u_0) ∈ L*(u_0) \ ?({u_1, u_2, …, u_{k-1}})，这给出了 {u_0, u_1, …, u_{k-2}} 的一个期望着色。

情形 2. ?(u_{k-1}) ≠ ?(u_k)。

我们固定一种颜色 α ∈ L*(u_0)，令 U_α := {u_i | 1 ≤ i ≤ k-2, α ∈ C(u_i)}。

如果 |U_α| ≥ 2，则我们对每个 u_i ∈ U_α 令 ?(u_i) = α，并对每个 u_i ∈ {u_1, u_2, …, u_{k-2}} \ U_α 选取 ?(u_i) ∈ C(u_i) \ {?(u_k)}。由于 |L*(u_0)| ≥ k-2 且 |?({u_1, u_2, …, u_{k-2}})| ≤ k-2-(|U_α|-1) ≤ k-3，我们可以选取 ?(u_0) ∈ L*(u_0) \ ?({u_1, u_2, …, u_{k-2}})。

由于 $\phi(u_{k-1}) \neq \phi(u_k)$ 且 $\alpha \neq \phi(u_k)$，我们有 $\phi(u_k) \in U_\phi(u_0, G)$，因此这就是一个所需的着色。因此，我们假设 $|U_\alpha| \leq 1$。然后我们令 $\phi(u_0) = \alpha$，并对每个 $u_i \in U_\alpha$（若 $U_\alpha \neq \emptyset$）选择 $\phi(u_i) \in C(u_i) \setminus \{\alpha\}$。由于 $\phi(u_{k-1}) \neq \phi(u_k)$ 且 $|U_\alpha| \leq 1$，$\phi(u_{k-1})$ 和 $\phi(u_k)$ 中至少有一个在 $u_0$ 周围恰好出现一次，设为 $\phi(u_k)$。对每个 $u_i \in \{u_1, u_2, \ldots, u_{k-2}\} \setminus U_\alpha$，我们选择 $\phi(u_i) \in C(u_i) \setminus \{\phi(u_k), \alpha\}$。由于 $\phi(u_k) \in U_\phi(u_0, G)$，这就是一个所需的着色。

现在我们对 $\bigcup_{i=1}^{k-2} \{v_i, w_i\}$ 中剩余的顶点进行着色。对每个 $i \in \{1, 2, \ldots, k-2\}$，我们首先选择 $\phi(v_i) \in L^*(v_i) \setminus \{\phi(u_0), \phi(u_i)\}$，然后选择 $\phi(w_i) \in L^*(w_i) \setminus \{\phi(v_i)\}$。由于 $\phi(u_i) \notin L^*(w_i)$，我们有 $U_\phi(v_i, G) \neq \emptyset$，因此 $\phi$ 是 $G$ 的一个正常无冲突 $L$-着色，矛盾。$\square$

**引理 3.6** 对任意 $k \geq 4$，若一个 $k$-顶点恰好与 $k-1$ 个 2-邻点相邻，则至多 $k-4$ 个 2-邻点包含在 $G$ 的 3-路径中。

**证明** 设 $u_0$ 为一个 $k$-顶点，其邻点为 $u_1, u_2, \ldots, u_k$，其中 $k \geq 4$。假设 $u_1, u_2, \ldots, u_{k-1}$ 是 2-顶点，且 $u_1, u_2, \ldots, u_{k-3}$ 中的每个顶点都包含在 $G$ 的一个 3-路径中。我们选取这样的顶点 $u_0$，使得度 $k$ 尽可能小。对每个 $i \in \{1, 2, \ldots, k-3\}$，设 $u_i v_i w_i$ 是包含 $u_i$ 的 3-路径，设 $x_i$ 为 $w_i$ 不同于 $v_i$ 的邻点。对 $i \in \{k-2, k-1\}$，设 $v_i$ 为 $u_i$ 不同于 $u_0$ 的邻点。由引理 3.3，对任意不同的 $i$ 和 $j$，$\{u_i, v_i, w_i, x_i\} \cap \{u_j, v_j, w_j\} = \emptyset$。令 $G' = G - \{u_0, u_{k-2}, u_{k-1}\} \cup \bigcup_{i=1}^{k-3} \{u_i, v_i, w_i\}$。若 $G'$ 有孤立顶点 $v$，则必有 $N_G(v) \subseteq \{u_0, u_{k-2}, u_{k-1}\} \cup \{w_1, w_2, \ldots, w_{k-3}\}$。由引理 3.4、引理 3.5 和 $k$ 的最小性，我们得出 $N_G(v) = \{u_k, u_{k-2}, u_{k-1}\} \cup \{w_1, w_2, \ldots, w_{k-3}\}$。这意味着 $G$ 同构于 $\Theta_{1,2 \star 2,3 \star 0,4 \star (k-3)}$，因此由命题 3.3 知 $G$ 是正常无冲突 $L$-可着色的，矛盾。

因此 $G'$ 没有孤立顶点。由命题 3.1 和 $G$ 的最小性，$G'$ 有一个正常无冲突 $L$-着色 $\phi$。对每个 $v \in \{u_k, v_{k-2}, v_{k-1}\} \cup \{x_1, x_2, \ldots, x_{k-3}\}$，设 $c_v$ 为 $U_\phi(v, G')$ 中的一个颜色。我们按如下方式定义剩余顶点的列表分配 $L^*$：

- 令 $L^*(u_0) = L(u_0) \setminus \{\phi(u_k), \phi(v_{k-2}), \phi(v_{k-1}), c_{u_k}\}$。
- 对每个 $i \in \{1, 2, \ldots, k-3\}$，令 $L^*(u_i) = L(u_i)$，$L^*(v_i) = L(v_i) \setminus \{\phi(x_i)\}$，且 $L^*(w_i) = L(w_i) \setminus \{\phi(x_i), c_{x_i}\}$。
- 对每个 $i \in \{k-2, k-1\}$，令 $L^*(u_i) = L(u_i) \setminus \{\phi(v_i), c_{v_i}\}$。

通过删除多余的颜色，我们可以假设对每个 $i \in \{1, 2, \ldots, k-3\}$ 有 $|L^*(u_i)| = 4$，$|L^*(v_i)| = 3$，$|L^*(w_i)| = 2$，且 $|L^*(u_{k-2})| = |L^*(u_{k-1})| = 2$。对每个 $i \in \{1, 2, \ldots, k-1\}$，令 $C(u_i)$ 为 $L^*(u_i) \setminus L^*(w_i)$ 中的两个颜色集合（若 $i \leq k-3$），令 $C(u_i) = L^*(u_i)$（若 $i \in \{k-2, k-1\}$）。与引理 3.5 的证明类似，我们将证明可以将 $\phi$ 正常地扩展到 $\{u_0, u_1, \ldots, u_{k-1}\}$，使得 $U_\phi(u_0, G) \neq \emptyset$ 且对每个 $i \in \{1, 2, \ldots, k-1\}$ 有 $\phi(u_i) \in C(u_i)$。

我们固定一个颜色 $\alpha \in L^*(u_0)$，令 $U_\alpha := \{u_i \mid 1 \leq i \leq k-1, \alpha \in C(u_i)\}$。注意由 $L^*(u_0)$ 的定义，$\alpha \neq \phi(u_k)$。

若 $|U_\alpha| \geq 3$，则我们令 $\phi(u_i) = \alpha$ 对每个 $u_i \in U_\alpha$，并对每个 $u_i \in \{u_1, u_2, \ldots, u_{k-1}\} \setminus U_\alpha$ 选择 $\phi(u_i) \in C(u_i) \setminus \{\phi(u_k)\}$。由于 $|L^*(u_0)| \geq k-2$ 且 $|\phi(\{u_1, u_2, \ldots, u_{k-1}\})| \leq k-1 - (|U_\alpha| - 1) \leq k-3$，我们可以选择 $\phi(u_0) \in L^*(u_0) \setminus \phi(\{u_1, u_2, \ldots, u_{k-1}\})$。显然我们有 $\phi(u_k) \in U_\phi(u_0, G)$，因此这就是一个所需的着色。

因此，我们假设 $|U_\alpha| \leq 2$。然后我们令 $\phi(u_0) = \alpha$，并对每个 $u_i \in U_\alpha$（若 $U_\alpha \neq \emptyset$）选择 $\phi(u_i) \in C(u_i) \setminus \{\alpha\}$。由于 $|\{u_k\} \cup U_\alpha| \leq 3$，$\{u_k\} \cup U_\alpha$ 的所有顶点要么都着同一种颜色 $\beta$，要么存在一种颜色 $\gamma$ 在 $\{u_k\} \cup U_\alpha$ 中恰好出现一次。

在前者情形中，我们选择 $\phi(u_{i_0}) \in C(u_{i_0}) \setminus \{\beta\}$ 对某个 $u_{i_0} \notin U_\alpha$，并令 $\phi(u_i) \in C(u_i) \setminus \{\phi(u_{i_0})\}$ 对每个 $u_i \in \{u_1, u_2, \ldots, u_{k-1}\} \setminus (U_\alpha \cup \{u_{i_0}\})$。由于 $\phi(u_{i_0}) \in U_\phi(u_0, G)$，这就是一个所需的着色。在后者情形中，对每个 $u_i \in \{u_1, u_2, \ldots, u_{k-1}\} \setminus U_\alpha$，我们选择 $\phi(u_i) \in C(u_i) \setminus \{\gamma\}$。然后，我们有 $\gamma \in U_\phi(u_0, G)$，因此这又是一个所需的着色。

通过与引理 3.5 证明中类似的论证，我们可以对 $\bigcup_{i=1}^{k-3} \{v_i, w_i\}$ 中剩余的顶点进行着色，得到 $G$ 的一个正常无冲突 $L$-着色，矛盾。$\square$

**引理 3.7** 设 $u_0$ 为一个 3-顶点，$N_G(u_0) = \{u_1, u_2, u_3\}$。若 $u_1$ 和 $u_2$ 都是 2-顶点，则它们各自的非 $u_0$ 邻点都是 4+ 顶点。

**证明** 对 $i = 1, 2$，设 $v_i$ 为 $u_i$ 不同于 $u_0$ 的邻点。由引理 3.1，$d_G(v_i) \geq 3$ 对 $i = 1, 2$。反设 $d_G(v_1) = 3$。我们可以假设 $|L(u_0)| = 5$ 且 $|L(u_1)| = |L(u_2)| = 4$。令 $G' = G - \{u_0, u_1, u_2\}$。若 $G'$ 有孤立顶点 $v$，则必有 $v = v_1 = v_2 = u_3$ 且 $V(G) = \{u_0, u_1, u_2, u_3\}$。这意味着 $G$ 同构于 $\Theta_{1,2 \star 2,3 \star 0,4 \star 0}$，且由命题 3.3 知 $G$ 是正常无冲突 $L$-可着色的，矛盾。因此 $G'$ 没有孤立顶点。设 $\phi$ 为 $G'$ 的一个正常无冲突 $L$-着色。对 $v \in \{u_3, v_2\}$，设 $c_v$ 为 $U_\phi(v, G')$ 中的一个颜色。

我们选择 $\phi(u_0) \in L(u_0) \setminus \{\phi(u_3), c_{u_3}, \phi(v_1), \phi(v_2)\}$，选择 $\phi(u_2) \in L(u_2) \setminus \{\phi(u_0), \phi(v_2), c_{v_2}\}$，然后选择 $\phi(u_1) \in L(u_1) \setminus \{\phi(u_0), \phi(v_1), \phi(u_2)\}$。由颜色的选择方式，$\phi$ 是一个正常的 $L$-着色，使得对每个 $v \in V(G) \setminus \{u_0, v_1\}$ 有 $U_\phi(v, G) \neq \emptyset$。$u_0$ 和 $v_1$ 各有三个邻点且至少有两种颜色，因此我们有 $U_\phi(u_0, G) \neq \emptyset$ 且 $U_\phi(v_1, G) \neq \emptyset$。因此 $\phi$ 是 $G$ 的一个正常无冲突 $L$-着色，矛盾。$\square$

**引理 3.8** 对 $k \in \{4, 5\}$，每个 $k$-顶点至多关联 $G$ 的 $k-2$ 条 2-路径。

**证明** 对整数 $k \in \{4, 5\}$，设 $u_0$ 为一个 $k$-顶点，其邻点为 $u_1, u_2, \ldots, u_k$。假设对每个 $i \in \{1, 2, \ldots, k-1\}$，$u_i$ 包含在 2-路径 $u_i v_i$ 中。我们固定这样的顶点 $u_0$，使得度 $k$ 尽可能小。设 $w_i$ 为 $v_i$ 不同于 $u_i$ 的邻点。令 $G' = G - \{u_0\} \cup \bigcup_{i=1}^{k-1} \{u_i, v_i\}$。由命题 3.1 和 $G$ 的最小性，$G'$ 有一个正常无冲突 $L$-着色 $\phi$。由引理 3.3，对任意不同的 $i$ 和 $j$，$\{u_i, v_i\} \cap \{u_j, v_j\} = \emptyset$。若 $G'$ 有孤立顶点 $v$，则必有 $N_G(v) \subseteq \{u_0, v_1, v_2, \ldots, v_{k-1}\}$。此外，由引理 3.4 和 $k$ 的最小性，可得 $N_G(v) = \{u_0, v_1, v_2, \ldots, v_{k-1}\}$。这意味着 $G$ 同构于 $\Theta_{1,2 \star 0,3 \star (k-1),4 \star 0}$，因此由命题 3.3 知 $G$ 是正常无冲突 $L$-可着色的，矛盾。

因此 $G'$ 没有孤立顶点。对每个 $v \in \{u_k, w_1, w_2, \ldots, w_{k-1}\}$，设 $c_v$ 为 $U_\phi(v, G')$ 中的一个颜色。我们按如下方式定义 $V(G) \setminus V(G')$ 的列表分配 $L^*$：

- 令 $L^*(u_0) = L(u_0) \setminus \{\phi(u_k), c_{u_k}\}$。
- 对 $i \in \{1, 2, \ldots, k-1\}$，令 $L^*(u_i) = L(u_i) \setminus \{\phi(w_i)\}$，且 $L^*(v_i) = L(v_i) \setminus \{\phi(w_i), c_{w_i}\}$。

通过删除多余的颜色，我们可以假设对每个 $i \in \{1, 2, \ldots, k-1\}$ 有 $|L^*(u_0)| = k$，$|L^*(u_i)| = 3$ 且 $|L^*(v_i)| = 2$。

对每个 $i \in \{1, 2, \ldots, k-2\}$，我们令 $\phi(u_i) \in L^*(u_i) \setminus L^*(v_i)$。注意此时 $u_0$ 有 $k-1 \in \{3, 4\}$ 个已着色的邻点。对剩余顶点，我们考虑以下两种情形。

**情形 1.** $|\phi(\{u_1, u_2, \ldots, u_{k-2}, u_k\})| \geq 3$。

我们首先选择 $\phi(u_0) \in L^*(u_0) \setminus \phi(\{u_1, u_2, \ldots, u_{k-2}\})$，选择 $\phi(v_{k-1}) \in L^*(v_{k-1}) \setminus \{\phi(u_0)\}$，并选择 $\phi(u_{k-1}) \in L^*(u_{k-1}) \setminus \{\phi(u_0), \phi(v_{k-1})\}$。然后，对每个 $i \in \{1, 2, \ldots, k-2\}$，令 $\phi(v_i) \in L^*(v_i) \setminus \{\phi(u_0)\}$。显然，$\phi$ 是 $G$ 的一个正常 $L$-着色。此外，由于 $d_G(u_0) \in \{4, 5\}$ 且邻点中至少出现三种颜色，我们有 $U_\phi(u_0, G) \neq \emptyset$，因此 $\phi$ 是 $G$ 的一个正常无冲突 $L$-着色，矛盾。

**情形 2.** $|\phi(\{u_1, u_2, \ldots, u_{k-2}, u_k\})| \leq 2$。

我们首先选择 $\phi(u_{k-1}) \in L^*(u_{k-1}) \setminus \phi(\{u_1, u_2, \ldots, u_{k-2}, u_k\})$，并选择 $\phi(v_{k-1}) \in L^*(v_{k-1}) \setminus \{\phi(u_{k-1})\}$。然后，由于 $\phi(u_k) \notin L^*(u_0)$，可得 $|L^*(u_0) \setminus \phi(\{u_1, u_2, \ldots, u_{k-2}, u_k\})| \geq |L^*(u_0)| - 1 \geq k-1 \geq 3$，因此我们可以选择 $\phi(u_0) \in L^*(u_0) \setminus (\phi(\{u_1, u_2, \ldots, u_{k-2}, u_k\}) \cup \{\phi(u_{k-1}), \phi(v_{k-1})\})$。最后，对每个 $i \in \{1, 2, \ldots, k-2\}$，令 $\phi(v_i) \in L^*(v_i) \setminus \{\phi(u_0)\}$。由颜色的选择方式，容易验证 $\phi$ 是 $G$ 的一个正常无冲突 $L$-着色，矛盾。$\square$

**引理 3.9** 设 $u_0$ 为一个 4-顶点，$N_G(u_0) = \{u_1, u_2, u_3, u_4\}$，使得 $d_G(u_1) = d_G(u_2) = d_G(u_3) = 2$。若 $u_1$ 和 $u_2$ 都包含在 $G$ 的 2-路径中，则 $u_3$ 的非 $u_0$ 邻点是一个 4+ 顶点。

**证明** 对每个 $i \in \{1, 2\}$，设 $u_i v_i$ 是包含 $u_i$ 的 $G$ 的 2-路径，设 $w_i$ 为 $v_i$ 不同于 $u_i$ 的邻点。设 $v_3$ 为 $u_3$ 不同于 $u_0$ 的邻点。假设 $d_G(v_3) \leq 3$。由引理 3.8，我们知道 $d_G(v_3) = 3$。

令 $G' = G - \{u_0, u_1, u_2, u_3, v_1, v_2\}$。若 $G'$ 有孤立顶点 $v$，则必有 $N_G(v) \subseteq \{u_0, u_3, v_1, v_2\}$。然而，由于 $d_G(v_3) = 3$，我们有 $d_G(v) \leq 3$，由引理 3.1（当 $d_G(v) = 3$ 时）或引理 3.3（当 $d_G(v) = 2$ 时）得到矛盾。

因此 $G'$ 没有孤立顶点。由命题 3.1 和 $G$ 的最小性，$G'$ 有一个正常无冲突 $L$-着色 $\phi$。注意 $v_3$ 在 $G'$ 中的两个邻点颜色不同。对每个 $v \in \{u_4, w_1, w_2\}$，设 $c_v$ 为 $U_\phi(v, G')$ 中的一个颜色。我们按如下方式定义列表分配 $L^*$：

- 令 $L^*(u_0) = L(u_0) \setminus \{\phi(u_4), \phi(v_3), c_{u_4}\}$。
- 对 $i \in \{1, 2\}$，令 $L^*(u_i) = L(u_i) \setminus \{\phi(w_i)\}$，且 $L^*(v_i) = L(v_i) \setminus \{\phi(w_i), c_{w_i}\}$。
- 令 $L^*(u_3) = L(u_3) \setminus \{\phi(v_3)\}$。

通过删除多余的颜色，我们可以假设 $|L^*(u_0)| = |L^*(u_1)| = |L^*(u_2)| = |L^*(u_3)| = 3$ 且 $|L^*(v_1)| = |L^*(v_2)| = 2$。

我们按以下方式将 $\phi$ 扩展为 $G$ 的一个 $L$-着色。我们首先令 $\phi(u_1) \in L^*(u_1) \setminus L^*(v_1)$ 和 $\phi(u_2) \in L^*(u_2) \setminus L^*(v_2)$，并令 $\phi(u_0) \in L^*(u_0) \setminus \{\phi(u_1), \phi(u_2)\}$。由于三个邻点 $\{u_1, u_2, u_4\}$ 已着色，$\{u_1, u_2, u_4\}$ 的所有顶点要么都着同一种颜色 $\alpha$，要么存在一种颜色 $\beta$ 在 $\{u_1, u_2, u_4\}$ 中恰好出现一次。在前者情形中，我们令 $\phi(u_3) \in L^*(u_3) \setminus \{\phi(u_0), \alpha\}$。在后者情形中，我们令 $\phi(u_3) \in L^*(u_3) \setminus \{\phi(u_0), \beta\}$。然后我们有 $U_\phi(u_0, G) \neq \emptyset$。最后，对 $i \in \{1, 2\}$，令 $\phi(v_i) \in L^*(v_i) \setminus \{\phi(u_0)\}$。由于 $v_3$ 是一个 3-顶点且其邻点中至少有两种不同颜色，我们有 $U_\phi(v_3, G) \neq \emptyset$。容易验证 $\phi$ 是 $G$ 的一个正常无冲突 $L$-着色，矛盾。$\square$

### 3.3 放电法

我们设置初始电荷 $c: V(G) \to \mathbb{R}$，对每个顶点 $v \in V(G)$ 令 $c(v) = 7d_G(v) - 18$。我们按照以下放电规则移动顶点的电荷。

**(R1)** 设 $u$ 为 $G$ 的一个 3-顶点。
- 若 $u$ 有两个 2-邻点，则 $u$ 向每个 2-邻点传送电荷 $3/2$。
- 若 $u$ 有一个 2-邻点，则 $u$ 向它传送电荷 $2$。

**(R2)** 设 $u$ 为 $G$ 的一个 4+ 顶点。
- $u$ 向每条关联的极大 3-路径中的每个顶点传送电荷 $2$。
- $u$ 向每条关联的极大 2-路径中的每个顶点传送电荷 $2$。
- $u$ 向相邻的具有除 $u$ 以外还有 3-邻点的 2-顶点传送电荷 $5/2$。
- $u$ 向相邻的具有除 $u$ 以外还有 4+ 邻点的 2-顶点传送电荷 $2$。

设 $c^*(v)$ 为放电后每个顶点 $v \in V(G)$ 的电荷。我们将证明对每个 $v \in V(G)$ 有 $c^*(v) \geq 0$。

**引理 3.10** 对每个 2-顶点 $v$，$c^*(v) \geq 0$。

**证明** 设 $P$ 是包含 $v$ 的 $G$ 的一条极大路径，它与两个 3+ 顶点 $x$ 和 $y$ 关联。由引理 3.2，$k := |V(P)| \leq 3$。

若 $k \in \{2, 3\}$，则由引理 3.1 知 $d_G(x) \geq 4$ 且 $d_G(y) \geq 4$。因此由 (R2)，$x$ 和 $y$ 各向 $v$ 传送电荷 $2$，因此 $c^*(v) = c(v) + 2 \times 2 = (14 - 18) + 4 = 0$。

假设 $k = 1$，即 $x$ 和 $y$ 是 $v$ 的两个邻点。若 $d_G(x) = d_G(y) = 3$，则引理 3.7 表明 $x$ 和 $y$ 都是恰好有一个 2-邻点的 3-顶点。因此由 (R1)，$x$ 和 $y$ 各向 $v$ 传送电荷 $2$，因此 $c^*(v) = c(v) + 2 \times 2 = (14 - 18) + 4 = 0$。因此，不失一般性，我们可以假设 $d_G(y) \geq 4$。然后由 (R1) 和 (R2)，$x$ 向 $v$ 传送至少 $3/2$ 的电荷，$y$ 向 $v$ 传送 $5/2$ 的电荷，因此 $c^*(v) \geq c(v) + 3/2 + 5/2 = (14 - 18) + 4 = 0$。$\square$

**引理 3.11** 对每个 3-顶点 $v$，$c^*(v) \geq 0$。

**证明** 由引理 3.4，$v$ 至多有两个 2-邻点。若 $v$ 有两个 2-邻点，则由 (R1) 得 $c^*(v) = c(v) - 2 \times 3/2 = (21 - 18) - 3 = 0$。否则，由 (R1) 得 $c^*(v) \geq c(v) - 2 = (21 - 18) - 2 > 0$。$\square$

**引理 3.12** 对每个 4+ 顶点 $v$，$c^*(v) \geq 0$。

**证明** 设 $v$ 为一个 $k$-顶点，其中 $k \geq 4$。我们定义 $n_0$、$n_1$、$n_2$ 和 $n_3$ 如下：

$$n_0 := |\{u \in N_G(v) \mid u \text{ 是具有除 } v \text{ 以外还有 4+ 邻点的 2-顶点}\}|,$$
$$n_1 := |\{u \in N_G(v) \mid u \text{ 是具有除 } v \text{ 以外还有 3-邻点的 2-顶点}\}|,$$
$$n_2 := |\{u \in N_G(v) \mid u \text{ 包含在 } G \text{ 的极大 2-路径中}\}|,$$
$$n_3 := |\{u \in N_G(v) \mid u \text{ 包含在 } G \text{ 的极大 3-路径中}\}|.$$

由引理 3.4，$v$ 至多有 $k-1$ 个 2-邻点，因此 $n_0 + n_1 + n_2 + n_3 \leq k-1$。根据放电规则 (R2)，我们有

$$c^*(v) = c(v) - 2n_0 - 5/2 \cdot n_1 - 4n_2 - 6n_3.$$

假设 $k = 4$。引理 3.5 和引理 3.8 分别意味着 $n_3 \leq 1$ 且 $n_2 + n_3 \leq 2$。若 $n_0 + n_1 + n_2 + n_3 = 3$，则引理 3.6 意味着 $n_3 = 0$。若 $n_0 + n_1 + n_2 + n_3 = 3$ 且 $n_2 = 2$，引理 3.9 意味着 $n_1 = 0$。根据这些论证，$v$ 周围只可能出现以下情形：

- $n_0 + n_1 + n_2 + n_3 \leq 2$ 且 $n_3 \leq 1$；
- $n_0 + n_1 + n_2 + n_3 = 3$，$n_2 \leq 1$，且 $n_3 = 0$；或
- $n_0 = 1$，$n_1 = 0$，$n_2 = 2$，且 $n_3 = 0$。

对每种情形，我们分别有 $c^*(v) \geq c(v) - 4 \times 1 - 6 \times 1 = (28 - 18) - 10 = 0$，$c^*(v) \geq c(v) - 5/2 \times 2 - 4 \times 1 = (28 - 18) - 9 > 0$，以及 $c^*(v) = c(v) - 2 \times 1 - 4 \times 2 = (28 - 18) - 10 = 0$。

假设 $k = 5$。引理 3.5 和引理 3.8 分别意味着 $n_3 \leq 2$ 且 $n_2 + n_3 \leq 3$。由引理 3.6，若 $n_0 + n_1 + n_2 + n_3 = 4$，则 $n_3 \leq 1$。因此，$v$ 周围只可能出现以下情形：

- $n_0 + n_1 + n_2 + n_3 \leq 3$ 且 $n_3 \leq 2$；或
- $n_0 + n_1 + n_2 + n_3 = 4$，$n_2 + n_3 \leq 3$，且 $n_3 \leq 1$。

对前者情形，我们有 $c^*(v) \geq c(v) - 4 \times 1 - 6 \times 2 = (35 - 18) - 16 > 0$。对后者情形，我们有 $c^*(v) \geq c(v) - 5/2 \times 1 - 4 \times 2 - 6 \times 1 = (35 - 18) - 33/2 > 0$。

最后，假设 $k \geq 6$。由引理 3.5 和引理 3.6，$v$ 周围只可能出现以下情形：

- $n_0 + n_1 + n_2 + n_3 \leq k-2$ 且 $n_3 \leq k-3$；或
- $n_0 + n_1 + n_2 + n_3 = k-1$ 且 $n_3 \leq k-4$。

对前者情形，我们有 $c^*(v) \geq c(v) - 4 \times 1 - 6 \times (k-3) = (7k - 18) - 4 - 6k + 18 = k - 4 > 0$。对后者情形，我们有 $c^*(v) \geq c(v) - 4 \times 3 - 6 \times (k-4) = (7k - 18) - 12 - 6k + 24 = k - 6 \geq 0$。$\square$

综合引理 3.10、引理 3.11 和引理 3.12，我们有

$$0 \leq \sum_{v \in V(G)} c^*(v) = \sum_{v \in V(G)} c(v) = \sum_{v \in V(G)} (7d_G(v) - 18) = 14|E(G)| - 18|V(G)|.$$

然而，这意味着 $\mathrm{mad}(G) \geq \frac{2|E(G)|}{|V(G)|} \geq \frac{18}{7}$，矛盾。这完成了定理 1.6 的证明。

### 4 结论性评论

在本文中，我们研究了有界最大平均度图的正常无冲突 $(d+k)$-可着色性。由于我们只有少数"不具有"正常无冲突 $(d+k)$-可着色性的例子（对于较小的 $k$），我们猜想以下关于猜想 1.2 和猜想 1.1 的公共强化仍然可能成立。

**猜想 4.1** 设 $G$ 为不同于 $C_5$ 的连通图，$L$ 为 $G$ 的一个列表分配，使得

$$|L(v)| = \begin{cases} 4 & \text{若 } d_G(v) = 2, \\ d_G(v) + 1 & \text{若 } d_G(v) \neq 2. \end{cases}$$

则 $G$ 是正常无冲突 $L$-可着色的。

Masaki Kashima | Riste ?krekovski | Rongxing Xu