稀疏图的列表单射边染色

List Injective Edge Coloring of Sparse Graphs

摘要: 图G的单射边染色是对图G的边进行染色，使得如果三条边e₁，e₂，e₃是连续的，那么e₁和e₃染不同的颜色。图G的单射边色数是所有单射边染色中所用颜色最少的颜色数。在本文中，我们考虑单射边染色的列表版本，得到在最大平均度条件限制下稀疏图的列表单射边色数的上界。

Abstract: An injective edge coloring of a graph G is a coloring of the edges of G, such that if three edges e₁, e₂, and e₃ are consecutive, then e₁ and e₃ are colored differently. The injective edge coloring number is the smallest number of colors used in all injective edge colorings of G. In this paper, we consider the list injective edge coloring of graphs, and obtain some upper bounds of the list injective edge coloring number of sparse graphs in terms of the maximum average degree of G.

1. 引言

图G的三条边e₁，e₂，e₃如果按此顺序形成一条长为3的路或一个3-圈，则称它们是连续的。图G的k-单射边染色是一个映射 $f:E\left(G\right)\to \left\{1,2,\cdots ,k\right\}$ ，使得如果边e₁，e₂，e₃是连续的，则 $f\left(e_1\right)\ne f\left(e_3\right)$ 。图G的单射边色数是所有单射边染色中所用颜色最少的颜色数，记为 ${{\chi }^{\prime }}_{inj}\left(G\right)$ 。单射边染色的概念是由Cardoso [1] 等为解决分组无线网络问题提出的，是单射点染色的推广。单射点染色是Hahn [2] 等人提出，用于编码理论和电脑网络 [3] 的设计。Jin [4] 等证明了确定图的单射色数是NP完全的。Cardoso [1] 等和Foucaud [5] 等分别考虑了单射边色数的计算复杂性，并证明了确定单射边色数是否不超过k是NP完全的。由此可得确定一般图的单射边色数的精确值是比较困难的，因此学者们通常研究特殊图的单射边色数 [6] [7] [8] [9] ，或者在给定条件限制下来研究单射边色数的上下界。如Kostochka [10] 等人在Hahn的研究基础上得到了在最大度限制下次立方图的单射边色数的上界。卜月华 [11] 等人考虑了在最大度以及最大平均度限制下稀疏图的单射边色数的上界，得到如下结果：

定理1对于 $\Delta \left(G\right)\le 3$ 的图G，有

(1) 若 $mad\left(G\right)<\frac{5}{2}$ ，则 ${{\chi }^{\prime }}_{inj}\left(G\right)\le 5$ ，

(2) 若 $mad\left(G\right)<\frac{18}{7}$ ，则 ${{\chi }^{\prime }}_{inj}\left(G\right)\le 6$ 。

定理2对于 $\Delta \left(G\right)\le 4$ 的图G，有

(1) 若 $mad\left(G\right)<\frac{22}{7}$ ，则 ${{\chi }^{\prime }}_{inj}\left(G\right)\le 12$ ，

(2) 若 $mad\left(G\right)<\frac{10}{3}$ ，则 ${{\chi }^{\prime }}_{inj}\left(G\right)\le 13$ ，

(3) 若 $mad\left(G\right)<\frac{18}{5}$ ，则 ${{\chi }^{\prime }}_{inj}\left(G\right)\le 14$ ，

(4) 若 $mad\left(G\right)<\frac{15}{4}$ ，则 ${{\chi }^{\prime }}_{inj}\left(G\right)\le 15$ 。

苗正科 [12] 等人得到了最大度为4，单射边色数不超过9，10，11，12的充分条件。本文在卜月华等人的研究基础上讨论在最大度及最大平均度限制下稀疏图的列表单射边色数的上界。令L是图G的边列表分配，即给每条边e分配可能的颜色集 $L\left(e\right)$ 。给定图G的边列表分配L，如果它有一个单射边染色f，使得对每条边 $e\in E\left(G\right)$ ，有 $f\left(e\right)\in L\left(e\right)$ ，则称图G是L-单射边可染的，f是图G的一个L-单射边染色。如果对于图G的每个边列表分配L，满足对每条边 $e\in E\left(G\right)$ ， $\left|L\left(e\right)\right|\ge k$ ，图G都是L-单射边可染的，则称图G是k-单射边可选的。使图G是k-单射边可选的最小的k值称为图G的列表单射边色数，记为 $c{h^{\prime }}_{inj}\left(G\right)$ 。显然，对于任意的图G有 ${{\chi }^{\prime }}_{inj}\left(G\right)\le c{h^{\prime }}_{inj}\left(G\right)$ 。Lv [6] 等人考虑了次立方图的列表单射边色数的上界。本文讨论 $\Delta \left(G\right)\le 3$ 和 $\Delta \left(G\right)\le 4$ 的稀疏图的列表单射边色数的上界，得到如下结果：

定理3对于 $\Delta \left(G\right)\le 3$ 的图G，有

(1) 若 $mad\left(G\right)<\frac{5}{2}$ ，则 $c{h^{\prime }}_{inj}\left(G\right)\le 5$ ，

(2) 若 $mad\left(G\right)<\frac{13}{5}$ ，则 $c{h^{\prime }}_{inj}\left(G\right)\le 6$ ，

(3) 若 $mad\left(G\right)<\frac{8}{3}$ ，则 $c{h^{\prime }}_{inj}\left(G\right)\le 7$ 。

定理4对于 $\Delta \left(G\right)\le 4$ 的图G，有

(1) 若 $mad\left(G\right)<\frac{19}{6}$ ，则 $c{h^{\prime }}_{inj}\left(G\right)\le 12$ ，

(2) 若 $mad\left(G\right)<\frac{17}{5}$ ，则 $c{h^{\prime }}_{inj}\left(G\right)\le 13$ ，

(3) 若 $mad\left(G\right)<\frac{18}{5}$ ，则 $c{h^{\prime }}_{inj}\left(G\right)\le 14$ ，

(4) 若 $mad\left(G\right)<\frac{15}{4}$ ，则 $c{h^{\prime }}_{inj}\left(G\right)\le 15$ 。

由于 ${{\chi }^{\prime }}_{inj}\left(G\right)\le c{h^{\prime }}_{inj}\left(G\right)$ ，定理3和定理4的结果对单射边色数也是成立的，因此我们的结果略微改进了卜月华等人的结果，并增加了列表单射边色数不超过7的充分条件。接下来我们先给出本文中需用到的基本概念和符号，然后给出定理3和定理4 (1)和(2)的证明。由于定理4 (3)和(4)的证明与定理2 (3)和(4)的证明几乎一致，本文我们省略了这两个证明。

2. 预备知识

设图G是一个有限的、简单的无向连通图，分别用 $V\left(G\right)$ ， $E\left(G\right)$ ， $\delta \left(G\right)$ 和 $\Delta \left(G\right)$ 来表示它的顶点集、边集、最小度和最大度。用 $d\left(v\right)$ 表示图G中顶点v的度数，如果 $d\left(v\right)=i$ ( $d\left(v\right)\ge i$ 或 $d\left(v\right)\le i$ )，则称v为i ( $i^{+}$ 或 $i^{-}$ )-点。用 $N\left(v\right)$ 表示v的邻点的集合，v的i ( $i^{+}$ 或 $i^{-}$ )-邻点表示v的一个度为i ( $i^{+}$ 或 $i^{-}$ )的邻点。用 $i_j$ -点表示与j个2-点相邻的i-点， $i^j$ -点表示与j个3-点相邻的i-点， $i_j^k$ -点表示与j个2-点、k个3-点相邻的i-点。如果两个顶点u，v与同一个i-点相邻，那么称这两个顶点u，v是i-弱相邻的。假设f是图G的一个部分边染色，对于边 $e\in E\left(G\right)$ ，用 $F_f\left(e\right)$ 表示染色过程中边e不能用的颜色集合，用 $L_f\left(e\right)$ 表示染色过程中e可用的颜色集合。

图G的最大平均度为 $mad\left(G\right)=\max \left\{\frac{2\left|E\left(H\right)\right|}{\left|V\left(H\right)\right|},H\subseteq G\right\}$ 。

若对于图G， $c{h^{\prime }}_{inj}\left(G\right)>k$ 且 $\forall H\subseteq G$ ， $c{h^{\prime }}_{inj}\left(H\right)\le k$ ，则称图G为列表单射边k-临界图。我们将用权转移法来进行定理的证明。权转移法的主要思想是：假设图G为列表单射边k-临界图，对G中每一个点v进行赋权，初始权重 $w\left(v\right)=d\left(v\right)$ 。假设有 $m>0$ ，使得 $mad\left(G\right)<m$ ，那么有

${\displaystyle \underset{v\in V\left(G\right)}{\sum }w\left(v\right)}={\displaystyle \underset{v\in V\left(G\right)}{\sum }d\left(v\right)}\le mad\left(G\right)\times \left|V\left(G\right)\right|<m\times \left|V\left(G\right)\right|$ . (1)

再按照设立的权转移规则重新分配权重。在重新分配后，若G中每一点v都有一个新的权重 $w^{*}\left(v\right)$ 使得 $w^{*}\left(v\right)\ge m$ ，那么

$m\times \left|V\left(G\right)\right|\le {\displaystyle \underset{v\in V\left(G\right)}{\sum }{w}^{*}\left(v\right)}={\displaystyle \underset{v\in V\left(G\right)}{\sum }w\left(v\right)}<m\times \left|V\left(G\right)\right|$ . (2)

出现矛盾，因此 $c{h^{\prime }}_{inj}\left(G\right)\le k$ 。

3. 定理3的证明

假设图G是列表单射边k-临界图， $k=5,6,7$ ， $\text{Δ}\left(G\right)\le 3$ ，我们将分别给出图G的结构性质，运用权转移法得到定理3的证明。

3.1. 定理3 (1)的证明

假设图G是列表单射边5-临界图，其中 $\Delta \left(G\right)\le 3$ ， $mad(G)<\frac{5}{2}$ 。设L是图G的边列表分配，满足对每条边 $e\in E\left(G\right)$ ， $\left|L\left(e\right)\right|=5$ ，且图G不是L-单射边可染的。则图G有下列性质：

引理1 $\delta \left(G\right)\ge 2$ 。

证明 假设图G中包含一个1-点v，设u为v的邻点。由G的极小性， $G^{\prime }=G-v$ 有一个L-单射边染色f。注意到 $\left|F_f\left(uv\right)\right|\le 4$ ，因此 $\left|L_f\left(uv\right)\right|\ge 1$ 。将边uv染 $L_f\left(uv\right)$ 中的颜色，可得到G的L-单射边染色，与假设矛盾。*

引理2 G中每个3-圈最多含有1个2-点。

证明 假设uvwu是G中的一个3-圈，u和v是两个2-点。由G的极小性， $G^{\prime }=G-\left\{u,v\right\}$ 有一个L-单射边染色f。由于 $\left|L_f\left(uw\right)\right|\ge 3$ ， $\left|L_f\left(vw\right)\right|\ge 3$ ， $\left|L_f\left(uv\right)\right|\ge 4$ ，因此可以依次给边uw，vw和uv染色，得到G的L-单射边染色，与假设矛盾。*

引理3 G中的2-点最多与1个2-点相邻。

证明 假设G中存在2-点u与2个2-点v和w相邻。由G的极小性， $G^{\prime }=G-u$ 有一个L-单射边染色f，则 $\left|L_f\left(uv\right)\right|\ge 2$ ， $\left|L_f\left(uw\right)\right|\ge 2$ ，因此可以依次给边uv和uw染色，得到G的L-单射边染色，与假设矛盾。*

引理4 G中的3-点最多与2个2-点相邻。

证明 假设G中存在3-点u与3个2-点 $v_1$ ， $v_2$ ， $v_3$ 相邻。由G的极小性， $G^{\prime }=G-u$ 有一个L-单射边染色f。根据引理2， $v_i\left(i=1,2,3\right)$ 不会在3-圈中，因此 $u{v}_1$ ， $u{v}_2$ ， $u{v}_3$ 可以染相同颜色。又由于 $\left|L_f\left(u{v}_1\right)\right|\ge 1$ ， $\left|L_f\left(u{v}_2\right)\right|\ge 1$ ， $\left|L_f\left(u{v}_3\right)\right|\ge 1$ ，因此可以依次给边 $u{v}_1$ ， $u{v}_2$ 和 $u{v}_3$ 染色，得到G的L-单射边染色，与假设矛盾。*

引理5 G中的3₂-点不与任意2-点2-弱相邻。

证明 假设G中存在3₂-点u与一个2-点2-弱相邻，设该2-点为v，w是u和v的公共邻点， $d\left(w\right)=2$ 。由G的极小性， $G^{\prime }=G-w$ 有一个L单射边染色f-。由于 $\left|L_f\left(uw\right)\right|\ge 1$ ， $\left|L_f\left(wv\right)\right|\ge 1$ ，且由引理2，uw和wv不在同一个3-圈中，可以染同种颜色，因此可以依次给边uw和wv染色，得到G的L-单射边染色，与假设矛盾。*

接下来对G中的每一个顶点v进行赋权，初始权重 $w\left(v\right)=d\left(v\right)$ 。

定义权转移规则如下：

$R_{11}$ ：每个3₁-点给相邻的2-点 $\frac{1}{2}$ 权重。

$R_{12}$ ：每个3₂-点给相邻的2-点 $\frac{1}{4}$ 权重。

对每个顶点 $v\in V\left(G\right)$ ，记 $w^{*}\left(v\right)$ 为新的权重。下面验证对每个顶点 $v\in V\left(G\right)$ ， $w^{*}\left(v\right)\ge \frac{5}{2}$ 。

如果v是2-点且与两个3-点相邻，那么由R₁₁，R₁₂有 $w^{*}\left(v\right)\ge 2+\frac{1}{4}\times 2=\frac{5}{2}$ 。如果v与一个2-点相邻，根据引理3，v的另一个邻点是3-点，设为顶点u。由引理5，u是3₁-点。因此，由 $R_{11}$ 有 $w^{*}\left(v\right)\ge 2+\frac{1}{2}=\frac{5}{2}$ 。

如果v是3-点，那么根据引理4，v最多与两个2-点相邻。因此，由R₁₁，R₁₂有 $w^{*}\left(v\right)\ge \min \left\{3-2\times \frac{1}{4},3-\frac{1}{2}\right\}=\frac{5}{2}$ 。

在(1)和(2)式中取 $m=\frac{5}{2}$ ，得到矛盾。因此 $c{h^{\prime }}_{inj}\left(G\right)\le 5$ ，定理3 (1)证毕。

3.2. 定理3 (2)的证明

注意到，当 $i\le j$ 时，列表单射边i-临界图的性质同样适用于列表单射边j-临界图。

假设图G是列表单射边6-临界图，其中 $\Delta \left(G\right)\le 3$ ， $mad\left(G\right)<\frac{13}{5}$ 。设L是图G的边列表分配，满足对每条边 $e\in E\left(G\right)$ ， $\left|L\left(e\right)\right|=6$ ，且图G不是L-单射边可染的。那么引理1至引理5的性质对图G仍成立，同时图G还具有以下性质：

引理6 G中每个3-圈不含有2-点。

证明 假设uwvu是G中的一个3-圈，其中 $d\left(u\right)=2$ 。由G的极小性， $G^{\prime }=G-u$ 有一个L-单射边染色f，则 $\left|L_f\left(uv\right)\right|\ge 2$ ， $\left|L_f\left(uw\right)\right|\ge 2$ ，因此可以依次给边uv和uw染色，得到G的L-单射边染色，与假设矛盾。*

引理7 G中不存在2个相邻的2-点。

证明 假设u和v是G中2个相邻的2-点，w是v的另一个邻点。由G的极小性， $G^{\prime }=G-v$ 有一个L-单射边染色f，则 $\left|L_f\left(uv\right)\right|\ge 2$ ， $\left|L_f\left(vw\right)\right|\ge 1$ 。因此可以依次给边vw和uv染色，得到G的L-单射边染色，与假设矛盾。*

引理8 G中2-点最多与1个3₂-点相邻。

证明 假设u是G中的一个2-点，与u相邻的两个顶点v和w都是3₂-点。由G的极小性， $G^{\prime }=G-u$ 有一个L-单射边染色f。根据引理6，uv和uw不在同一个3-圈中，因此可以染相同颜色。又由于v和w都是3₂-点， $\left|L_f\left(uv\right)\right|\ge 1$ ， $\left|L_f\left(uw\right)\right|\ge 1$ 。因此可以依次给边uv和uw染色，得到G的L-单射边染色，与假设矛盾。*

接下来对G中的每一个顶点v进行赋权，初始权重 $w\left(v\right)=d\left(v\right)$ 。

定义权转移规则如下：

$R_{21}$ ：每个3₁-点给相邻的2-点 $\frac{2}{5}$ 权重。

$R_{22}$ ：每个3₂-点给相邻的2-点 $\frac{1}{5}$ 权重。

对每个顶点 $v\in V\left(G\right)$ ，记 $w^{*}\left(v\right)$ 为新的权重。下面检验对任意 $v\in V\left(G\right)$ ， $w^{*}\left(v\right)\ge \frac{13}{5}$ 。

如果v是2-点，则由引理7、引理8以及 $R_{21}$ 、 $R_{22}$ ， $w^{*}\left(v\right)\ge 2+\frac{1}{5}+\frac{2}{5}=\frac{13}{5}$ 。

假设v是3-点。如果v是3₁-点，则根据 $R_{21}$ 有 $w^{*}\left(v\right)=3-\frac{2}{5}=\frac{13}{5}$ 。如果v是3₂-点，则根据 $R_{22}$ 有 $w^{*}\left(v\right)=3-\frac{1}{5}\times 2=\frac{13}{5}$ 。

在(1)和(2)式中取 $m=\frac{13}{5}$ ，得到矛盾。因此 $c{h^{\prime }}_{inj}\left(G\right)\le 6$ ，定理3 (2)证毕。

3.3. 定理3 (3)的证明

假设图G是列表单射边7-临界图，其中 $\Delta \left(G\right)\le 3$ ， $mad\left(G\right)<\frac{8}{3}$ 。设L是图G的边列表分配，满足对每条边 $e\in E\left(G\right)$ ， $\left|L\left(e\right)\right|=7$ ，且图G不是L-单射边可染的。则列表单射边6-临界图的性质对图G仍成立，且图G还具有以下性质：

引理9 G中不存在3₂-点。

证明 假设G中存在3₂-点u，v₁，v₂和v₃是u的邻点且 $d\left(v_1\right)=d\left(v_2\right)=2$ 。由G的极小性， $G^{\prime }=G-u$ 有一个L-单射边染色f。则 $\left|L_f\left(u{v}_1\right)\right|\ge 2$ ， $\left|L_f\left(u{v}_2\right)\right|\ge 2$ ， $\left|L_f\left(u{v}_3\right)\right|\ge 1$ ，根据引理6， $u{v}_1$ ， $u{v}_2$ ， $u{v}_3$ 中任意2条边不会在同一个3-圈中，因此 $u{v}_1$ ， $u{v}_2$ ， $u{v}_3$ 可以染相同颜色，依次给边 $u{v}_1$ ， $u{v}_2$ 和 $u{v}_3$ 染色，可以得到G的L-单射边染色，与假设矛盾。*

接下来对G中的每一个顶点v进行赋权，初始权重 $w\left(v\right)=d\left(v\right)$ 。

定义权转移规则如下：

$R_{31}$ ：每个3₁-点给相邻的2-点 $\frac{1}{3}$ 权重。

对每个顶点 $v\in V\left(G\right)$ ，记 $w^{*}\left(v\right)$ 为新的权重。下面验证对每个顶点 $v\in V\left(G\right)$ ， $w^{*}\left(v\right)\ge \frac{8}{3}$ 。

如果v是2-点，则由引理7，v不与2-点相邻，再由引理9，2-点只与3₁-点相邻，由 $R_{31}$ 有 $w^{*}\left(v\right)=2+2\times \frac{1}{3}=\frac{8}{3}$ 。

如果v是3-点，则根据 $R_{31}$ 有 $w^{*}\left(v\right)\ge 3-\frac{1}{3}=\frac{8}{3}$ 。

在(1)和(2)式中取 $m=\frac{8}{3}$ ，得到矛盾。因此 $c{h^{\prime }}_{inj}\left(G\right)\le 7$ ，定理3 (3)证毕。

4. 定理4的证明

本节给出定理4 (1)和(2)的证明。假设图G是列表单射边k-临界图， $k=12,13$ ， $\Delta \left(G\right)\le 4$ ，我们将分别给出图G的结构性质，运用权转移法得到证明。

4.1. 定理4 (1)的证明

假设图G是列表单射边12-临界图，其中 $\Delta \left(G\right)\le 4$ ， $mad\left(G\right)<\frac{19}{6}$ 。设L是图G的边列表分配，满足对每条边 $e\in E\left(G\right)$ ， $\left|L\left(e\right)\right|=12$ ，且图G不是L-单射边可染的。则图G有以下性质：

引理10 $\delta \left(G\right)\ge 2$ 。

证明 该证明类似引理1的证明，故略去。*

引理11 (1) G中的每个3-圈不含有2-点；(2) G中没有3-点在3个3-圈中。

证明 (1) 该证明类似引理6的证明，故略去。

(2) 假设G中存在1个3-点u在3个3-圈中，v，w和x是u的3个邻点。由G的极小性， $G^{\prime }=G-u$ 有一个L-单射边染色f。则 $\left|L_f\left(uv\right)\right|\ge 4$ ， $\left|L_f\left(uw\right)\right|\ge 4$ ， $\left|L_f\left(ux\right)\right|\ge 4$ ，因此可以给边uv，uw和ux染不同颜色，得到G的L-单射边染色，与假设矛盾。*

引理12 (1) G中的2-点只与4-点相邻；(2) G中的4-点最多与1个2-点相邻。

证明 (1) 假设G中存在1个2-点u，v和w是u的邻点，且v是 $3^{-}$ -点。由G的极小性， $G^{\prime }=G-u$ 有一个L-单射边染色f。则 $\left|L_f\left(uv\right)\right|\ge 3$ ， $\left|L_f\left(uw\right)\right|\ge 1$ ，因此可以依次染uw，uv，得到G的L-单射边染色，与假设矛盾。

(2) 假设G中存在1个4-点u与2个2-点相邻。设v和w是u的2个2-邻点，x是v的另一个邻点。由G的极小性， $G^{\prime }=G-v$ 有一个L-单射边染色f。首先，去掉边uw上的颜色。根据引理11，uv，uw和vx不在任何3-圈中，因此 $\left|L_f\left(vx\right)\right|\ge 1$ 。我们先给vx染色，此时 $\left|L_f\left(uv\right)\right|\ge 2$ ， $\left|L_f\left(uw\right)\right|\ge 2$ ，所以可以依次染uv，uw，得到G的L-单射边染色，与假设矛盾。*

引理13 G中的4₁-点最多与2个3-点相邻。

证明 假设G中存在1个4₁-点u与3个3-点v，w，x相邻。设u的另一个2-邻点为y，y的另一个邻点记为z。由G的极小性， $G^{\prime }=G-y$ 有一个L-单射边染色f。首先我们去掉边ux上的颜色。则 $\left|L_f\left(yz\right)\right|\ge 1$ ， $\left|L_f\left(uy\right)\right|\ge 3$ ， $\left|L_f\left(ux\right)\right|\ge 2$ ，因此可以依次染边yz，ux，uy，得到G的L-单射边染色，与假设矛盾。*

引理14 G中的2-点最多与1个 $4_1^2$ -点相邻。

证明 假设G中存在1个2-点u，它的2个邻点v和w均为 $4_1^2$ -点。由G的极小性， $G^{\prime }=G-u$ 有一个L-单射边染色f。由于 $\left|L_f\left(uv\right)\right|\ge 2$ ， $\left|L_f\left(uw\right)\right|\ge 2$ ，因此可以依次染边uv，uw，得到G的L-单射边染色，与假设矛盾。*

引理15 G中的每个3-圈最多包含2个3-点。

证明 假设G中存在1个3-圈uvwu，且 $d\left(u\right)=d\left(v\right)=d\left(w\right)=3$ 。设u，v，w在3-圈之外的邻点分别是 $u_1$ ， $v_1$ ， $w_1$ 。

如果 $u_1$ ， $v_1$ ， $w_1$ 两两均不重合，那么由G的极小性， $G^{\prime }=G-u$ 有一个L-单射边染色f。首先，去掉边vw上的颜色。此时 $\left|L_f\left(u{u}_1\right)\right|\ge 1$ ， $\left|L_f\left(uv\right)\right|\ge 5$ ， $\left|L_f\left(uw\right)\right|\ge 5$ ， $\left|L_f\left(vw\right)\right|\ge 6$ ，我们可以依次染边 $u{u}_1$ ，uv，uw，vw，得到G的L-单射边染色，与假设矛盾。

如果 $u_1$ ， $v_1$ ， $w_1$ 有重合，那么根据引理11，在 $\left\{u_1,v_1,w_1\right\}$ 中最多有2个点重合。不妨设 $v_1=w_1=x$ 。由G的极小性， $G^{\prime }=G-u$ 有1个L-单射边染色f。首先，去掉边vw上的颜色。此时 $\left|L_f\left(u{u}_1\right)\right|\ge 1$ ， $\left|L_f\left(uv\right)\right|\ge 6$ ， $\left|L_f\left(uw\right)\right|\ge 6$ ， $\left|L_f\left(vw\right)\right|\ge 8$ ，我们可以依次染边 $u{u}_1$ ，uv，uw，vw，得到G的L-单射边染色，与假设矛盾。*

引理16 G中的3-点最多与2个3-点相邻。

证明 假设G中存在1个3-点u与3个3-点v，w，x相邻。由G的极小性， $G^{\prime }=G-u$ 有一个L-单射边染色f。由于u，v，w，x都是3-点，根据引理15，u不在G的任意一个3-圈内，因此uv，uw，ux可以染相同颜色。又由于 $\left|L_f\left(uv\right)\right|\ge 2$ ， $\left|L_f\left(uw\right)\right|\ge 2$ ， $\left|L_f\left(ux\right)\right|\ge 2$ ，故我们可以依次染边uv，uw，ux，得到G的L-单射边染色，与假设矛盾。*

下面对G中的每一个顶点v进行赋权，初始权重 $w\left(v\right)=d\left(v\right)$ 。

定义权转移规则如下：

$R_{41}$ ：每个2-点从与它相邻的 $4_1^0,4_1^1$ -点获得 $\frac{2}{3}$ 权重。

$R_{42}$ ：每个2-点从与它相邻的 $4_1^2$ -点获得 $\frac{1}{2}$ 权重。

$R_{43}$ ：每个3-点从与它相邻的4-点获得 $\frac{1}{6}$ 权重。

接下来，我们检查对任意 $v\in V\left(G\right)$ ，新的权重 $w^{*}\left(v\right)\ge \frac{19}{6}$ 。

如果v是2-点，则根据引理12，v有2个4-邻点，且这2个4-邻点都是4₁-点。根据引理13、引理14， $R_{41}$ 和 $R_{42}$ 有 $w^{*}\left(v\right)\ge 2+\frac{1}{2}+\frac{2}{3}=\frac{19}{6}$ 。

如果v是3-点，则根据引理16，v至少与1个4-点相邻，由 $R_{43}$ 有 $w^{*}\left(v\right)\ge 3+\frac{1}{6}=\frac{19}{6}$ 。

如果v是4-点，则根据引理12，v只能是4₁-点或4₀-点。如果v是4₁-点，那么根据引理13，v只能是 $4_1^0$ -点、 $4_1^1$ -点或 $4_1^2$ -点。当v是 $4_1^0$ 或 $4_1^1$ -点时， $w^{*}\left(v\right)\ge 4-\frac{1}{6}-\frac{2}{3}=\frac{19}{6}$ ；当v是 $4_1^2$ -点时， $w^{*}\left(v\right)=4-\frac{1}{2}-\frac{1}{6}\times 2=\frac{19}{6}$ 。如果v是4₀-点，则由 $R_{43}$ 有 $w^{*}\left(v\right)\ge 4-\frac{1}{6}\times 4=\frac{20}{6}>\frac{19}{6}$ 。

于是在(1)和(2)式中取 $m=\frac{19}{6}$ ，得到矛盾。因此 $c{h^{\prime }}_{inj}\left(G\right)\le 12$ ，定理4 (1)证毕。

4.2. 定理4 (2)的证明

假设图G是列表单射边13-临界图，其中 $\Delta \left(G\right)\le 4$ ， $mad\left(G\right)<\frac{17}{5}$ 。设L是图G的边列表分配，满足对每条边 $e\in E\left(G\right)$ ， $\left|L\left(e\right)\right|=13$ ，且图G不是L-单射边可染的。如果1个顶点u仅与1个4-点相邻，那么我们称u为坏点，否则称u为好点。因为图G是列表单射边13-临界图，所以引理10至引理16的性质对图G仍然成立，且图G还具有以下性质：

引理17 $\delta \left(G\right)\ge 3$ 。

证明 假设G中存在2-点u，设v和w是u的2个邻点。由G的极小性， $G^{\prime }=G-u$ 有一个L-单射边染色f。则 $\left|L_f\left(uv\right)\right|\ge 1$ ， $\left|L_f\left(uw\right)\right|\ge 1$ ，且由引理11，uv，uw不在同一个3-圈中，因此可以染相同颜色，于是依次染uv，uw，可以得到G的L-单射边染色，与假设矛盾。*

引理18 (1) G中的3-点最多在1个3-圈中；(2) G中每个3-圈最多含有1个3-点。

证明 (1) 假设G中存在3-点u在两个3-圈中，v，w，x是u的3个邻点。不妨设 $vw\in E\left(G\right)$ ， $vx\in E\left(G\right)$ 。由G的极小性， $G^{\prime }=G-u$ 有一个L-单射边染色f。则 $\left|L_f\left(uv\right)\right|\ge 4$ ， $\left|L_f\left(uw\right)\right|\ge 2$ ， $\left|L_f\left(ux\right)\right|\ge 2$ 。所以可以依次染边uw，uv，ux得到G的L-单射边染色，与假设矛盾。

(2) 假设G中含有3-圈uvwu，且 $d\left(u\right)=d\left(v\right)=3$ 。设u在3-圈外的邻点为x。由G的极小性， $G^{\prime }=G-u$ 有一个L-单射边染色f。首先，去掉边vw上的颜色，则 $\left|L_f\left(ux\right)\right|\ge 1$ ， $\left|L_f\left(uw\right)\right|\ge 3$ ， $\left|L_f\left(wv\right)\right|\ge 4$ ， $\left|L_f\left(uv\right)\right|\ge 5$ 。因此我们可以依次染边ux，uw，wv，uv，得到G的L-单射边染色，与假设矛盾。*

引理19 G中的4-点最多与3个3-点相邻。

证明 假设G中存在4-点u与4个3-点相邻，设u的邻点分别为x，w，v，y。由G的极小性， $G^{\prime }=G-u$ 有一个L-单射边染色f。则 $\left|L_f\left(ux\right)\right|\ge 1$ ， $\left|L_f\left(uw\right)\right|\ge 1$ ， $\left|L_f\left(uv\right)\right|\ge 1$ ， $\left|L_f\left(uy\right)\right|\ge 1$ 。根据引理18，ux，uw，uv，uy中任何2条边都不会在同一个3-圈中，因此它们可以染相同颜色。所以可以依次染边ux，uw，uv，uy，得到G的L-单射边染色，与假设矛盾。*

引理20 G中任意2个坏的3-点不相邻。

证明 假设u，v是G中的2个坏的3-点，且 $uv\in E\left(G\right)$ 。设 $u_1$ 和 $v_1$ 分别是与u和v相邻的3-点， $u_2$ 和 $v_2$ 分别是与u和v相邻的4-点。由G的极小性， $G^{\prime }=G-v$ 有一个L-单射边染色f。首先，去掉边 $u{u}_1$ 的颜色，则 $\left|L_f\left(v{v}_2\right)\right|\ge 1$ ， $\left|L_f\left(uv\right)\right|\ge 3$ ， $\left|L_f\left(v{v}_1\right)\right|\ge 3$ ， $\left|L_f\left(u{u}_1\right)\right|\ge 4$ 。因此，我们可以依次染边 $v{v}_2$ ， $uv$ ， $v{v}_1$ ， $u{u}_1$ ，得到G的L-单射边染色，与假设矛盾。*

引理21 如果G中存在1个坏的3-点v，v₁，v₂是v的2个3-邻点，则在 $N\left(v_i\right)\backslash \left\{v\right\}\left(i=1,2\right)$ 中至少存在1个好点。

证明 假设w和x是v₁的除v外的2个邻点，且w和x都是坏点。根据引理20，v₁是好点，又由引理16，v₁的邻点不能都是3-点，因此w和x都是4-点。由G的极小性， $G^{\prime }=G-v_1$ 有一个L-单射边染色f。若 $v_{1}w$ ， $v_{1}x$ 不在同一个3-圈中，则 $\left|L_f\left(v{v}_1\right)\right|\ge 2$ ， $\left|L_f\left(v_{1}w\right)\right|\ge 1$ ， $\left|L_f\left(v_{1}x\right)\right|\ge 1$ ，且 $v_{1}w$ ， $v_{1}x$ 可以染相同颜色，因此可以依次染 $v_{1}w$ ， $v_{1}x$ ， $v{v}_1$ 得到G的L-单射边染色，与假设矛盾。若 $v_{1}w$ ， $v_{1}x$ 在同一个3-圈中，则 $\left|L_f\left(v{v}_1\right)\right|\ge 3$ ， $\left|L_f\left(v_{1}w\right)\right|\ge 4$ ， $\left|L_f\left(v_{1}x\right)\right|\ge 4$ ，因此可以依次染边 $v{v}_1$ ， $v_{1}w$ ， $v_{1}x$ ，得到G的L-单射边染色，与假设矛盾。所以w和x至少存在1个好点。同理， $N\left(v_2\right)\backslash \left\{v\right\}$ 中至少存在1个好点。*

引理22 如果G中存在1个好的4-点v，w是v的3-邻点，则w的邻点中至多有1个坏的3-点。

证明 由于w与1个4-点v相邻，因此w最多有2个3-邻点。若w有2个坏的3-邻点，则w也是坏点，因此存在2个坏的3-点相邻，与引理20矛盾。所以w的邻点中至多有1个坏的3-点。*

接下来对G中的每一个顶点v进行赋权，初始权重 $w\left(v\right)=d\left(v\right)$ 。

定义权转移规则如下：

$R_{51}$ ：每个3-点从与它相邻的4-点获得 $\frac{1}{5}$ 权重。

$R_{52}$ ：每个坏的3-点从与它3-弱相邻的好的4-点获得 $\frac{1}{10}$ 权重。

接下来，我们检查对任意 $v\in V\left(G\right)$ ，新的权重 $w^{*}\left(v\right)\ge \frac{17}{5}$ 。

如果v是3-点，则由引理16，v至少与1个4-点相邻。若v与恰好1个4-点相邻，即v是坏点，根据引理21，v的每个3-邻点都至少与1个好的4-点相邻。由 $R_{52}$ ，v从与它3-弱相邻的好的4-点获得 $\frac{1}{10}$ 权重。又因为v有2个相邻的3-点，于是 $w^{*}\left(v\right)\ge 3+\frac{1}{10}\times 2+\frac{1}{5}=\frac{17}{5}$ 。若v与至少2个4-点相邻，则由 $R_{51}$ 有 $w^{*}\left(v\right)\ge 3+\frac{1}{5}\times 2=\frac{17}{5}$ 。

如果v是4-点，则由引理19，v至少与1个4-点相邻。若v是坏点，则由 $R_{51}$ 有 $w^{*}\left(v\right)\ge 4-\frac{1}{5}\times 3=\frac{17}{5}$ 。若v是好点，则v最多与2个3-点相邻，由引理22，每个3-点最多与1个坏的3-点相邻，因此v最多与2个坏的3-点3-弱相邻。由 $R_{51}$ ， $R_{52}$ 有 $w^{*}\left(v\right)\ge 4-\frac{1}{5}\times 2-\frac{1}{10}\times 2=\frac{17}{5}$ 。

于是在(1)和(2)式中取 $m=\frac{17}{5}$ ，得到矛盾。因此 $c{h^{\prime }}_{inj}\left(G\right)\le 13$ ，定理4 (2)证毕。

基金项目

福建省自然科学基金(2020J05058)，华侨大学中央高校基本科研业务费专项资金(ZQN-903)。

NOTES

$$

^*通讯作者。