稀疏图的

摘要

图$\mathrm{G}$的$k$-frugal列表色数一般记作$\mathrm{c}{\mathrm{h}}_k\left(G\right)$，关于稀疏的$k$-frugal列表色数上界，有以下3个结论：$\forall k\ge \mathrm{3}$，如果图$G$满足$\mathrm{m}\mathrm{a}\mathrm{d}\left(G\right)<\mathrm{3}-a$（其中$\mathrm{0}<a\le \frac{\mathrm{1}}{\mathrm{3}}$）且$\mathrm{\Delta }\left(G\right)\ge k+\frac{\mathrm{3}}{a}-\mathrm{3}$，则$\mathrm{c}{\mathrm{h}}_k\left(G\right)=⌈\frac{∆}{k-\mathrm{1}}⌉+\mathrm{1}$；$\forall k\ge \mathrm{4}$，如果图$\mathrm{G}$满足$\mathrm{m}\mathrm{a}\mathrm{d}\left(G\right)<\mathrm{3}$，则$\mathrm{c}{\mathrm{h}}_k\left(G\right)\le ⌈\frac{∆}{k-\mathrm{1}}⌉+\mathrm{2}$；$\forall k\ge \mathrm{4}$，如果图$\mathrm{G}$满足$\mathrm{m}\mathrm{a}\mathrm{d}\left(G\right)<\frac{\mathrm{10}}{\mathrm{3}}$，则$\mathrm{c}{\mathrm{h}}_k\left(G\right)\le ⌈\frac{∆}{k-\mathrm{1}}⌉+\mathrm{3}$。

关键词

图论; 染色; 最大平均度; 平面图; 围长

本文仅讨论无向的有限的简单图，未提及的定义和定理参见文献［1］。对于一个点$v$，用$d_G(v)$、$N_G(v)$（不造成歧义的情况下可以简写为$d(v)$、$N(v)$）来定义点$v$的度数和点$v$的邻点集合。对于图$G$，分别用$V(G)$、$E(G)$、$\mathrm{\Delta }(G)$、$\delta (G)$和$g(G)$来定义它的点集、边集、最大度、最小度和围长（图$G$中最小圈的长度）。将平面图嵌入平面后，用$F(G)$表示其面集，一个$k^{+}$-点（或$k^{-}$-点）$v$表示点$v$的度数至少为$k$ （或至多为$k$）。类似的，用$d_G(f)$表示面$f$的度数，一个$k^{+}$-面（或$k^{-}$-面）$f$表示点$f$的度数至少为$k$ （或至多为$k$）。

图$G$的一个正常$k$-染色指的是从点集$V(G)$到颜色集$\{\mathrm{1,2},...,k\}$的映射$c$，使得图$G$中任意相邻的两点均不同色。用$c(v)$定义点$v$的颜色，用$C_i(v)$定义在$N(v)$中出现过$i$次的颜色所构成的集合。

图$G$的最大平均度一般记作$\mathrm{m}\mathrm{a}\mathrm{d}(G)$，定义为$\mathrm{m}\mathrm{a}\mathrm{d}\left(G\right)=\mathrm{m}\mathrm{a}\mathrm{x}\left\{\frac{\mathrm{2}\left|E\left(H\right)\right|}{\left|V\left(H\right)\right|}\right\}H\subseteq G\}$。

图的frugal-染色首先由Hind等人在文献［2］中提出。在图$G$的一个点染色$c$中，如果每种颜色在点$v$的邻点中至多出现$k-\mathrm{1}$次，就称点$v$是$k$-frugal的。如果图$G$中每个点都是$k$-frugal的，就称图$G$是$k$-frugal可染的，这个染色称作图$G$的$k$-frugal染色。图$G$的$k$-frugal色数，记作${\chi }_k(G)$，指的是使图$G$满足$k$-frugal可染所需的最少的颜色数量。由定义易知，${\chi }_k(G)\ge ⌈\frac{\mathrm{\Delta }}{k-\mathrm{1}}⌉+\mathrm{1}$。

图的frugal-染色可以推广到列表染色上。设$L$为一个函数，它将图$G$中的每个点$v$都映射到一个由一些正整数构成的集合$L(v)$上，$L(v)$称作点$v$的列表。如果一个染色$c:V\to N$满足$c(v)\in L(v)$对于所有$v\in V$都成立，就称这个染色为图$G$关于$L$的列表染色，或$L$-染色，并且称图$G$是$L$-可染的。如果图$G$中每个点的列表长度均满足$|L\left(v\right)|=l$，就称这个列表为图$G$的$l$-列表。如果对于任意$l$-列表$L$，图$G$都是$k$-frugal $L$-可染的，则满足这个条件的最小正整数$l$就称作图$G$的$k$-frugal 列表色数，记作$c{h}_k\left(G\right)$。

图$G$的linear $k$-染色是图的一种特殊的正常$k$-染色。linear染色的定义是由Yuster^［3］首先提出的，要求图$G$中由任意两种颜色导出的子图，均为若干条内部不相交的路。图$G$的linear-色数，记作$lc(G)$，指的是使图$G$满足linear $k$-染色所需要的最小整数$k$。

显然，一个linear染色必定为3-frugal染色，但是反过来并不一定成立，因为linear染色中不允许双色圈的存在。更多关于linear染色的结果参见文献［4-9］。

图$G$的2-distance $k$-染色是图的另一种特殊的正常$k$-染色。2-distance染色的定义是由Wegner^［10］首先提出的，要求图$G$中距离小于等于2的两个点均不同色。图$G$的2-distance-色数，指的是使图$G$满足2-distance $k$-染色所需要的最小整数$k$。

显然，2-distance染色的定义2-frugal染色的定义相同。更多关于2-distance染色的结果参见文献［11-24］。

关于一般的$k$-frugal染色，Amini等人在文献［25］中证明了对于任意$k\ge \mathrm{1}$，平面图$G$都满足

$${\chi }_k\le \left\{\begin{array}{c}⌈\frac{\mathrm{\Delta }-\mathrm{1}}{k-\mathrm{1}}⌉+\mathrm{2},g\ge \mathrm{7}\mathrm{且}\mathrm{\Delta }\ge \mathrm{1}\mathrm{190}+\mathrm{2}k\\ ⌈\frac{\mathrm{\Delta }+\mathrm{4}}{k-\mathrm{1}}⌉+\mathrm{6},g\ge \mathrm{6}\\ ⌈\frac{\mathrm{\Delta }+\mathrm{10}}{k-\mathrm{1}}⌉+\mathrm{6},g\ge \mathrm{5}\end{array}\right.$$

Fang和Zhang在在文献［26］中证明了：对于任意$k\ge \mathrm{4}$，如果平面图G不含4-圈和5-圈，则$\mathrm{c}{\mathrm{h}}_k\left(G\right)\le ⌈\frac{∆}{k-\mathrm{1}}⌉+\mathrm{5}$。对于任意$k\ge \mathrm{4}$，如果平面图G不含4-圈和5-圈且最大度满足$\mathrm{\Delta }\ge \mathrm{3}k+\mathrm{8}$，则$\mathrm{c}{\mathrm{h}}_k\left(G\right)\le ⌈\frac{∆}{k-\mathrm{1}}⌉+\mathrm{2}$。

1 主要结论

下面讨论稀疏图的$k$-frugal列表染色，并得出如下结论。

定理1.1.  　$\forall k\ge \mathrm{3}$，如果图$G$满足$\mathrm{m}\mathrm{a}\mathrm{d}\left(G\right)<\mathrm{3}-a$（其中$\mathrm{0}<a\le \frac{\mathrm{1}}{\mathrm{3}}$）且$\mathrm{\Delta }\left(G\right)\ge k+\frac{\mathrm{3}}{a}-\mathrm{3}$，则$\mathrm{c}{\mathrm{h}}_k\left(G\right)=⌈\frac{∆}{k-\mathrm{1}}⌉+\mathrm{1}$。

定理1.2.  　$\forall k\ge \mathrm{4}$，如果图$G$满足$\mathrm{m}\mathrm{a}\mathrm{d}\left(G\right)<\mathrm{3}$，则$\mathrm{c}{\mathrm{h}}_k\left(G\right)\le ⌈\frac{∆}{k-\mathrm{1}}⌉+\mathrm{2}$。

定理1.3.  　$\forall k\ge \mathrm{4}$，如果图$G$满足$\mathrm{m}\mathrm{a}\mathrm{d}\left(G\right)<\frac{\mathrm{10}}{\mathrm{3}}$，则$\mathrm{c}{\mathrm{h}}_k\left(G\right)\le ⌈\frac{∆}{k-\mathrm{1}}⌉+\mathrm{3}$。

对于平面图$G$，其最大平均度和围长之间满足$\mathrm{m}\mathrm{a}\mathrm{d}\left(G\right)<\frac{\mathrm{2}g\left(G\right)}{g\left(G\right)-\mathrm{2}}$，因此由上述3个定理，可以得到以下推论。

推论1.1.  　$\forall \mathrm{k}\ge \mathrm{3}$，如果图$G$的围长满足$g\left(G\right)\ge ⌈\frac{\mathrm{6}-\mathrm{2}a}{\mathrm{1}-a}⌉$（其中$\mathrm{0}<a\le \frac{\mathrm{1}}{\mathrm{3}}$），最大度满足$\mathrm{\Delta }\left(G\right)\ge k+\frac{\mathrm{3}}{a}-\mathrm{3}$，则$\mathrm{c}{\mathrm{h}}_k\left(G\right)=⌈\frac{∆}{k-\mathrm{1}}⌉+\mathrm{1}$。

推论1.2.  　$\forall k\ge \mathrm{4}$，如果图$G$的围长满足$g\left(G\right)\ge \mathrm{6}$，则$\mathrm{c}{\mathrm{h}}_k\left(G\right)\le ⌈\frac{∆}{k-\mathrm{1}}⌉+\mathrm{2}$。

推论1.3.  　$\forall k\ge \mathrm{4}$，如果图$G$的围长满足$g\left(G\right)\ge \mathrm{5}$，则$\mathrm{c}{\mathrm{h}}_k\left(G\right)\le ⌈\frac{∆}{k-\mathrm{1}}⌉+\mathrm{3}$。

2 定理1.1的证明

反证法，假设定理不成立，图$G_{\mathrm{0}}$是一个反例，即平面图$G_{\mathrm{0}}$满足$\mathrm{m}\mathrm{a}\mathrm{d}\left(G\right)<\mathrm{3}-a$，$\mathrm{\Delta }\left(G_{\mathrm{0}}\right)\ge k+\frac{\mathrm{3}}{a}-\mathrm{3}$，且$\mathrm{c}{\mathrm{h}}_k\left(G_{\mathrm{0}}\right)>⌈\frac{∆(G_{\mathrm{0}})}{k-\mathrm{1}}⌉+\mathrm{1}$。设$L$为一个$(⌈\frac{∆(G_{\mathrm{0}})}{k-\mathrm{1}}⌉+\mathrm{1})$-列表，图$G_{\mathrm{0}}$在此列表下不可染。在本节的证明中，约定$∆(G_{\mathrm{0}})$即为$∆$。取集合$G$$=\left\{\mathrm{G}\right\}\mathrm{G}\subseteq {\mathrm{G}}_{\mathrm{O}},∆\left(G\right)\le ∆\left(G_{\mathrm{0}}\right)=∆,\mathrm{m}\mathrm{a}\mathrm{d}\left(G\right)\le \mathrm{m}\mathrm{a}\mathrm{d}\left(G_{\mathrm{0}}\right),\mathrm{c}{\mathrm{h}}_k\left(G\right)>⌈\frac{∆(G_{\mathrm{0}})}{k-\mathrm{1}}⌉+\mathrm{1}\}$，由$G_O\in G$知该集合不是空集。那么，在此集合中取边数最小的图$G$，则图$\mathrm{c}{\mathrm{h}}_k\left(G\right)>⌈\frac{∆(G_{\mathrm{0}})}{k-\mathrm{1}}⌉+\mathrm{1}$，从而知道，对于$(⌈\frac{∆(G_{\mathrm{0}})}{k-\mathrm{1}}⌉+\mathrm{1})$-列表$L$，图$G$在此列表下是不可染的，但是其任意真子图都是$L$-可染的。

下面首先证明图$G$的一些结构，然后通过Discharging的方法来证明这个结论。

引理2.1.  　$\delta (G)\ge \mathrm{2}$。

证明：　反证法，假设图$G$含有一个1-点$v$。由图$G$的定义知，$G-v$有一个$k$-frugal $L$-染色$c$。设$N_G\left(v\right)=u$，此时若想把染色扩充到图$G$上，点$v$禁用的颜色为$c(u)$以及在$N_G\left(u\right)$中出现过$k-\mathrm{1}$次的颜色（即$C_{k-\mathrm{1}}(u)$）。因此禁用的颜色至多为

$$\mathrm{1}+⌊\frac{\mathrm{d}\left(u\right)-\mathrm{1}}{k-\mathrm{1}}⌋=⌈\frac{\mathrm{d}\left(u\right)}{k-\mathrm{1}}⌉<⌈\frac{\mathrm{\Delta }}{k-\mathrm{1}}⌉+\mathrm{1}$$

因此，可以将染色扩充到图$G$上，矛盾。

引理2.2.  　对于图$G$中任意一个${(k-\mathrm{1})}^{-}$-点$v$，设$N_G\left(v\right)=\{v_{\mathrm{1}},v_{\mathrm{2}},\dots ,v_x\}$，则有${\sum }_{i=\mathrm{1}}^x⌈\frac{\mathrm{d}\left(v_i\right)}{k-\mathrm{1}}⌉\ge ⌈\frac{∆}{k-\mathrm{1}}⌉+\mathrm{1}$。

证明：　反证法，假设引理不成立，则${\sum }_{i=\mathrm{1}}^x⌈\frac{\mathrm{d}(v_i)}{k-\mathrm{1}}⌉<⌈\frac{∆}{k-\mathrm{1}}⌉+\mathrm{1}$。

由图$G$的定义知，$G-v$有一个$k$-frugal $L$-染色$c$。此时若想把染色扩充到图$G$上，点$v$禁用的颜色为诸$c(v_i)$以及在$N_G(v_i)$中出现过$k-\mathrm{1}$次的颜色（即$C_{k-\mathrm{1}}(v_i)$）。因此禁用的颜色至多为

$$x+{\displaystyle \sum _{i=\mathrm{1}}^x}⌊\frac{\mathrm{d}\left(v_i\right)-\mathrm{1}}{k-\mathrm{1}}⌋={\displaystyle \sum _{i=\mathrm{1}}^x}⌈\frac{\mathrm{d}(v_i)}{k-\mathrm{1}}⌉<⌈\frac{∆}{k-\mathrm{1}}⌉+\mathrm{1}$$

这样就可以将染色扩充到图$G$上，矛盾。

为了方便证明，下面给出一些定义。

如果一个2-点$v$和另外一个2-点相邻，就称其为轻2-点，否则就称为非轻2-点。设$v$为一个2-点，$N_G\left(v\right)=\{v_{\mathrm{1}},v_{\mathrm{2}}\}$且$\mathrm{d}\left(v_{\mathrm{1}}\right)\le k-\mathrm{1}$，则由引理2.2，$\mathrm{d}\left(v_{\mathrm{2}}\right)\ge ∆-\left(k-\mathrm{2}\right)\ge k+\frac{\mathrm{3}}{a}-\mathrm{3}-\left(k-\mathrm{2}\right)=\frac{\mathrm{3}-a}{a}$。定义${(\frac{\mathrm{3}-a}{a})}^{+}$-点为${∆}^{\epsilon }$-点。

下面通过Discharging的方法得到一个矛盾。给每个点$v$赋初始权$\omega \left(v\right)=d(v)$，因此有

$$\sum _{x\in \mathrm{V}}\omega \left(x\right)=\mathrm{2}|E|\le \mathrm{m}\mathrm{a}\mathrm{d}(G)\times |V|$$

对于每个$x\in \mathrm{V}$，都通过特定的权转移规则（权只能从一个元素转移到另一个元素，故总和不变），得到一个新权${\omega }^{*}\left(x\right)$，因为在权转移的过程中总和不变，所以仍有

$$\sum _{x\in \mathrm{V}}{\omega }^{*}\left(x\right)=\mathrm{2}|E|$$

如果在权转移后，得到${\omega }^{*}\left(x\right)>\mathrm{m}\mathrm{a}\mathrm{d}(G)$对于所有$x\in V$均成立，则有

$$\sum _{x\in \mathrm{V}}{\omega }^{*}\left(x\right)>\mathrm{m}\mathrm{a}\mathrm{d}(G)\times |V|$$

这样就得到一个矛盾，从而定理得证。

下面给出权转移规则，Discharging 规则：

每个${\mathrm{3}}^{+}$-点$v$转移$\frac{\mathrm{d}\left(v\right)-(\mathrm{3}-a)}{\mathrm{d}(v)}$到相邻的2-点。下面来验证${\omega }^{*}\left(x\right)\ge \mathrm{3}-a$对于所有$x\in \mathrm{V}$均成立。对于${\mathrm{3}}^{+}$-点$v$，容易验证${\omega }^{*}\left(v\right)\ge \mathrm{3}-a$。

下面来讨论2-点，对于轻2-点$v$，容易验证${\omega }^{*}\left(v\right)\ge \mathrm{2}+\frac{\left[\frac{\mathrm{3}-a}{a}-\left(\mathrm{3}-a\right)\right]}{\frac{\mathrm{3}-a}{a}}=\mathrm{2}+(\mathrm{1}-a)=\mathrm{3}-a$。

对于非轻2-点$v$，设$N_G\left(v\right)=\{x,y\}$且$\mathrm{3}\le \mathrm{d}(x)\le \mathrm{d}(y)$，则由引理2.2知，$⌈\frac{\mathrm{d}\left(x\right)}{k-\mathrm{1}}⌉+⌈\frac{\mathrm{d}\left(y\right)}{k-\mathrm{1}}⌉\ge ⌈\frac{∆}{k-\mathrm{1}}⌉+\mathrm{1}$。

设$⌈\frac{\mathrm{d}\left(x\right)}{k-\mathrm{1}}⌉=p+\mathrm{1}$，即$p(k-\mathrm{1})+\mathrm{1}\le \mathrm{d}(x)\le (p+\mathrm{1})(k-\mathrm{1})$；设$⌈\frac{\mathrm{d}\left(y\right)}{k-\mathrm{1}}⌉=q+\mathrm{1}$，即$q(k-\mathrm{1})+\mathrm{1}\le \mathrm{d}(y)\le (q+\mathrm{1})(k-\mathrm{1})$，则$⌈\frac{∆}{k-\mathrm{1}}⌉+\mathrm{1}\le p+q+\mathrm{2}$，故$∆\le (p+q+\mathrm{1})(k-\mathrm{1})$。可以得到$\mathrm{d}(x)+\mathrm{d}(y)-\mathrm{2}\ge (p+q)(k-\mathrm{1})\ge ∆-(k-\mathrm{1})$，即$\mathrm{d}\left(x\right)+\mathrm{d}\left(y\right)\ge ∆-k+\mathrm{3}=\frac{\mathrm{3}}{a}$。

现在有${\omega }^{*}\left(v\right)\ge \mathrm{2}+\frac{\mathrm{d}\left(x\right)-(\mathrm{3}-a)}{\mathrm{d}(x)}+\frac{\mathrm{d}\left(y\right)-(\mathrm{3}-a)}{\mathrm{d}(y)}=\mathrm{4}-\left(\mathrm{3}-a\right)(\frac{\mathrm{1}}{\mathrm{d}(x)}+\frac{\mathrm{1}}{\mathrm{d}(y)})$，由$\mathrm{3}\le \mathrm{d}(x)\le d(y)$知，$\mathrm{d}(x)=\mathrm{3}$时${\omega }^{*}\left(v\right)$取得最小值，又由$\mathrm{d}\left(y\right)\ge \frac{\mathrm{3}}{a}-\mathrm{d}(x)$，从而，${\omega }^{*}\left(v\right)\ge \mathrm{4}-\left(\mathrm{3}-a\right)(\frac{\mathrm{1}}{\mathrm{3}}+\frac{\mathrm{1}}{\frac{\mathrm{3}}{a}-\mathrm{3}})$。下面希望证明${\omega }^{*}\left(v\right)\ge \mathrm{3}-a$。令$f\left(a\right)=\mathrm{4}-\left(\mathrm{3}-a\right)\left(\frac{\mathrm{1}}{\mathrm{3}}+\frac{\mathrm{1}}{\frac{\mathrm{3}}{a}-\mathrm{3}}\right)-\left(\mathrm{3}-a\right)=\frac{a}{\mathrm{3}}\times \frac{\mathrm{1}-\mathrm{3}a}{\mathrm{1}-a}$， 而当$\mathrm{0}<a\le \frac{\mathrm{1}}{\mathrm{3}}$时$f(a)\ge \mathrm{0}$，此即对于任意非轻2-点$v$，有${\omega }^{*}\left(v\right)\ge \mathrm{3}-a$。

综上，得到了一个矛盾，定理得证。

3 定理1.2的证明

反证法，假设定理不成立，图$G$取边数最小的极小反例，则图$c{h}_k\left(G\right)>⌈\frac{∆(G_{\mathrm{0}})}{k-\mathrm{1}}⌉+\mathrm{2}$。设$L$为一个$(⌈\frac{∆(G_{\mathrm{0}})}{k-\mathrm{1}}⌉+\mathrm{2})$-列表，则图$G$在此列表下不是$k$-frugal可染的，但是其任意真子图都是$L$-可染的。

下面首先证明图$G$的一些结构，然后通过discharging的方法来证明这个结论。

引理3.1.  　$\delta (G)\ge \mathrm{2}$。

证明：　证明方法与引理2.1相同。

引理3.2.  　$G$中不含与${\mathrm{3}}^{-}$-点相邻的$\mathrm{2}$-点。

证明：　假设定理不成立，$G$中存在一个2-点$v$，且其与一个${\mathrm{3}}^{-}$-点$u$相邻。由于图$G$为极小反例，$G-v$有一个$k$-frugal $L$-染色$c$。设$N_G\left(v\right)=\{u,w\}$，则$v$禁用的颜色为$c(u)$，$c(w)$以及在$N_G(w)$中出现过$k-\mathrm{1}$次的颜色（i.e. $C_{k-\mathrm{1}}(w)$），所以点$v$禁用的颜色至多为

$$\mathrm{1}+\mathrm{1}+⌊\frac{\mathrm{d}\left(w\right)-\mathrm{1}}{k-\mathrm{1}}⌋=⌈\frac{\mathrm{d}(w)}{k-\mathrm{1}}⌉+\mathrm{1}\le ⌈\frac{∆}{k-\mathrm{1}}⌉+\mathrm{1},$$

因此，可以将染色$c$扩充到图$G$上，矛盾。

引理3.3.  　$G$中不含与3个$\mathrm{2}$-点相邻的$\mathrm{4}$-点。

证明：　假设定理不成立，$G$中含有一个$\mathrm{4}$-点$v$，且其与3个$\mathrm{2}$-点$x$，$y$，$z$相邻。设$x_{\mathrm{1}}$，$y_{\mathrm{1}}$，$z_{\mathrm{1}}$分别为$x$，$y$，$z$的另一个邻点，$v_{\mathrm{1}}$为$v$的第4个邻点。由于$G$为极小反例，$G-\{v,x,y,z\}$有一个$k$-frugal $L$-染色$c$。设点$w\in \{v,x,y,z\}$，则$w$禁用的颜色为$c(w_{\mathrm{1}})$以及在$N_G(w_{\mathrm{1}})$出现过$k-\mathrm{1}$次的颜色（i.e. $C_{k-\mathrm{1}}(w_{\mathrm{1}})$），因此点$w$禁用的颜色为

$$\mathrm{1}+⌊\frac{\mathrm{d}\left(w_{\mathrm{1}}\right)-\mathrm{1}}{k-\mathrm{1}}⌋=⌈\frac{\mathrm{d}(w_{\mathrm{1}})}{k-\mathrm{1}}⌉\le ⌈\frac{∆}{k-\mathrm{1}}⌉,$$

设$L^{*}\left(w\right)=L\left(w\right)\backslash (\left\{c\left(w_{\mathrm{1}}\right)\right\}\bigcup C_{k-\mathrm{1}}(w_{\mathrm{1}}))$，则$\left|L^{*}\left(w\right)\right|\ge \mathrm{2}$，其中，$w\in \{v,x,y,z\}$。

首先用$c(x)\in L^{*}\left(x\right)\backslash \{c(v_{\mathrm{1}})\}$中的颜色染$x$，用$c(v)\in L^{*}\left(v\right)\backslash \{c(x)\}$中的颜色染$v$，用$c(y)\in L^{*}\left(y\right)\backslash \{c(v)\}$中的颜色染$y$，用$c(z)\in L^{*}\left(z\right)\backslash \{c(v)\}$中的颜色染$z$。容易验证这是图$G$的一个$k$-frugal $L$-染色，矛盾。

引理3.4.  　$G$中不含与5个$\mathrm{2}$-点相邻的$\mathrm{5}$-点。

证明：　假设定理不成立，$G$中含有一个$\mathrm{5}$-点$v$，且$N_G\left(v\right)=\{x_{\mathrm{1}},x_{\mathrm{2}},\dots ,x_{\mathrm{5}}\}$，$d_G\left(x_i\right)=\mathrm{2}$，$y_i$为$x_i$的另一个邻点（其中$i=\mathrm{1},\mathrm{2},\dots ,\mathrm{5}$）。由于$G$为极小反例，$G\backslash \{v,x_{\mathrm{1}},x_{\mathrm{2}},\dots ,x_{\mathrm{5}}\}$有一个$k$-frugal $L$-染色$c$。$\forall \mathrm{1}\le i\le \mathrm{5}$，点$x_i$禁用的颜色为$c(y_i)$和在$N_G(y_i)$中出现过$k-\mathrm{1}$次的颜色（i.e. $C_{k-\mathrm{1}}(y_i)$）。设$L^{*}\left(x_i\right)=L\left(x_i\right)\backslash (\left\{c\left(y_i\right)\right\}\bigcup C_{k-\mathrm{1}}(y_i))$，易得$\left|L^{*}\left(x_i\right)\right|\ge ⌈\frac{∆}{k-\mathrm{1}}⌉+\mathrm{2}-(\mathrm{1}+⌊\frac{d\left(y_i\right)-\mathrm{1}}{k-\mathrm{1}}⌋)\ge \mathrm{2}$。对于点$v$，易得$\left|L\left(v\right)\right|\ge ⌈\frac{∆}{k-\mathrm{1}}⌉+\mathrm{2}\ge \mathrm{3}$。

下面将染色$c$扩充到图$G$上。

首先用$L^{*}\left(x_{\mathrm{1}}\right)$中的颜色染$x_{\mathrm{1}}$，这个颜色记作$a$；然后用$L^{*}\left(x_{\mathrm{2}}\right)\backslash \{a\}$中的颜色染$x_{\mathrm{2}}$，这个颜色记作$c\left(x_{\mathrm{2}}\right)$；用$L^{*}\left(v\right)\backslash \{a,c\left(x_{\mathrm{2}}\right)\}$中的颜色染$v$，这个颜色记作$b$；最后用$L^{*}\left(x_i\right)\backslash \{b\}$中的颜色染$x_i$，其中$i=\mathrm{3,4},\mathrm{5}$。容易验证当$c\left(x_{\mathrm{3}}\right)=c\left(x_{\mathrm{4}}\right)=c\left(x_{\mathrm{5}}\right)=a$和$c\left(x_{\mathrm{3}}\right)=c\left(x_{\mathrm{4}}\right)=c\left(x_{\mathrm{5}}\right)=c\left(x_{\mathrm{2}}\right)$均不成立的时候，这个染色为图$G$的$k$-frugal $L$-染色。不失一般性，假定$L^{*}\left(x_i\right)=\{a,b\}$且$c\left(x_i\right)=a$对于$i=\mathrm{3,4},\mathrm{5}$均成立。

如果$L^{*}\left(x_{\mathrm{1}}\right)\ne \{a,b\}$，那么可以用$L^{*}\left(x_{\mathrm{1}}\right)\backslash \{a\}$中的颜色给$x_{\mathrm{1}}$重新染色，容易验证这是图$G$的$k$-frugal $L$-染色。

下面假设$L^{*}\left(x_{\mathrm{1}}\right)=\{a,b\}$。重新给$x_{\mathrm{1}}$和$x_{\mathrm{5}}$染上颜色$b$，用$c\left(v\right)\in L\left(v\right)\backslash \{a,b\}$中的颜色重新染$v$，用$L^{*}\left(x_{\mathrm{2}}\right)\backslash \{c(v)\}$中的颜色重新染$x_{\mathrm{2}}$，容易验证这是图$G$的一个$k$-frugal $L$-染色，矛盾。

接下来通过discharging的方法来获得一个矛盾，首先给每个点$v$赋初始权$\omega \left(v\right)=d(v)$，设权转移后得到的新权围${\omega }^{*}\left(v\right)$。

下面给出权转移规则，每个${\mathrm{4}}^{+}$-点$v$转移$\frac{\mathrm{1}}{\mathrm{2}}$到相邻的2-点。

下面来验证${\omega }^{*}\left(x\right)\ge \mathrm{3}$对于所有$x\in \mathrm{V}$均成立。

设$v$为一个$k$-点。

如果$k\ge \mathrm{6}$，则$\omega \left(v\right)\ge d\left(v\right)-\frac{\mathrm{1}}{\mathrm{2}}d\left(v\right)=\frac{\mathrm{1}}{\mathrm{2}}d\left(v\right)\ge \mathrm{3}$。

如果$k=\mathrm{5}$，由引理3.4，$\mathrm{5}$点之至多只能与4个$\mathrm{2}$-点相邻，则$\omega \left(v\right)\ge \mathrm{5}-\mathrm{4}\times \frac{\mathrm{1}}{\mathrm{2}}=\mathrm{3}$。

如果$k=\mathrm{4}$，由引理3.3，$\mathrm{4}$点之至多只能与2个$\mathrm{2}$-点相邻，则$\omega \left(v\right)\ge \mathrm{4}-\mathrm{2}\times \frac{\mathrm{1}}{\mathrm{2}}=\mathrm{3}$。

如果$k=\mathrm{3}$，由引理3.2，$\mathrm{3}$点之不与$\mathrm{2}$-点相邻，则$\omega \left(v\right)\ge \mathrm{3}$。

如果$k=\mathrm{2}$，由引理3.2，$\mathrm{2}$-点只能与${\mathrm{4}}^{+}$-点相邻，则$\omega \left(v\right)\ge \mathrm{2}+\mathrm{2}\times \frac{\mathrm{1}}{\mathrm{2}}=\mathrm{3}$。

综上，得到了一个矛盾，定理得证。

4 定理1.3的证明

反证法，假设定理不成立，图$G$取边数最小的极小反例，则图$\mathrm{c}{\mathrm{h}}_k\left(G\right)>⌈\frac{∆(G_{\mathrm{0}})}{k-\mathrm{1}}⌉+\mathrm{3}$。设$L$为一个$(⌈\frac{∆(G_{\mathrm{0}})}{k-\mathrm{1}}⌉+\mathrm{3})$-列表，则图$G$在此列表下不是$k$-frugal可染的，但是其任意真子图都是$L$-可染的。

下面首先证明图$G$的一些结构，然后通过discharging的方法来证明这个结论。

引理4.1.  　$\delta (G)\ge \mathrm{2}$。

证明：　证明方法与引理2.1相同。

引理4.2.  　对于图$G$中任意一个${(k-\mathrm{1})}^{-}$-点$v$，设$N_G\left(v\right)=\{v_{\mathrm{1}},v_{\mathrm{2}},\dots ,v_x\}$，则有${\sum }_{i=\mathrm{1}}^x⌈\frac{d\left(v_i\right)}{k-\mathrm{1}}⌉\ge ⌈\frac{∆}{k-\mathrm{1}}⌉+\mathrm{3}$。

证明：　证明方法与引理2.2相同。

引理4.3.  　若$v$为$\mathrm{2}$-点且$N_G\left(v\right)=\{\mathrm{u},\mathrm{w}\}$，$\mathrm{d}(\mathrm{u})\le \mathrm{d}(\mathrm{w})$，则$d\left(u\right)\ge \mathrm{2}\left(k-\mathrm{1}\right)+\mathrm{1}\ge \mathrm{7}$。

证明：　假设$d\left(u\right)\le \mathrm{2}\left(k-\mathrm{1}\right)$，带入引理4.2，得$\mathrm{d}\left(\mathrm{w}\right)>∆$，矛盾。

引理4.4.  　若$v$为$\mathrm{3}$-点，$N_G\left(v\right)=\{\mathrm{x},y,z\}$，且$\mathrm{d}(\mathrm{x})\le \mathrm{d}(\mathrm{y})\le \mathrm{d}(\mathrm{z})$，则$d(z)\ge d(y)\ge k\ge \mathrm{4}$。

证明：　假设$d\left(y\right)\le k-\mathrm{1}$，带入引理4.2，得$\mathrm{d}\left(\mathrm{z}\right)>∆$，矛盾。

引理4.5.  　不存在与6个$\mathrm{2}$-点相邻的$\mathrm{7}$-点。

证明：　设$v$为一个$\mathrm{7}$-点，$N_G\left(v\right)=\{x_{\mathrm{1}},x_{\mathrm{2}},x_{\mathrm{3}},x_{\mathrm{4}},x_{\mathrm{5}},x_{\mathrm{6}},u\}$，其中$d\left(x_i\right)=\mathrm{2}$，$N_G\left(x_i\right)=\{v,y_i\}$（$i=\mathrm{1},\mathrm{2},\dots ,\mathrm{6}$）。

由图$G$的极小性，图$G-\{v,x_{\mathrm{1}},x_{\mathrm{2}},x_{\mathrm{3}},x_{\mathrm{4}},x_{\mathrm{5}},x_{\mathrm{6}}\}$有一个$k$-frugal $L$-染色$c$。此时点$v$被禁用的颜色为$c(u)$以及在$N_G\left(u\right)$中出现$k-\mathrm{1}$次的颜色。因此点$v$被禁用的颜色至多为

$$\mathrm{1}+⌊\frac{\mathrm{d}\left(u\right)-\mathrm{1}}{k-\mathrm{1}}⌋=⌈\frac{\mathrm{d}(u)}{k-\mathrm{1}}⌉\le ⌈\frac{∆}{k-\mathrm{1}}⌉$$

设点$v$的可用颜色集为$L^{*}\left(v\right)$，则$\left|L^{*}\left(v\right)\right|\ge \mathrm{3}$。

同理可得

点$x_i\in \{x_{\mathrm{1}},x_{\mathrm{2}},x_{\mathrm{3}},x_{\mathrm{4}},x_{\mathrm{5}},x_{\mathrm{6}}\}$的可用颜色集为$\left|L^{*}\left(x_i\right)\right|\ge \mathrm{3}$。

下面将这个染色c扩充到图$G$上。

给$x_{\mathrm{1}}$染颜色$c_{\mathrm{1}}\in L^{*}\left(x_{\mathrm{1}}\right)\backslash \{c(u)\}$，给$x_{\mathrm{2}}$染颜色$c_{\mathrm{2}}\in L^{*}\left(x_{\mathrm{2}}\right)\backslash \{c\left(u\right),c_{\mathrm{1}}\}$，给$v$染颜色$c_{\mathrm{3}}\in L^{*}\left(v\right)\backslash \{c_{\mathrm{1}},c_{\mathrm{2}}\}$。

给$x_{\mathrm{3}}$染颜色$a_{\mathrm{1}}\in L^{*}\left(x_{\mathrm{3}}\right)\backslash \{c_{\mathrm{3}}\}$，给$x_{\mathrm{4}}$染颜色$b_{\mathrm{1}}\in L^{*}\left(x_{\mathrm{4}}\right)\backslash \{c_{\mathrm{3}},a_{\mathrm{1}}\}$。

给$x_{\mathrm{5}}$染颜色$a_{\mathrm{2}}\in L^{*}\left(x_{\mathrm{5}}\right)\backslash \{c_{\mathrm{3}}\}$，给$x_{\mathrm{6}}$染颜色$b_{\mathrm{2}}\in L^{*}\left(x_{\mathrm{6}}\right)\backslash \{c_{\mathrm{3}},a_{\mathrm{2}}\}$。

因此，$a_{\mathrm{1}}\ne b_{\mathrm{1}}$，$a_{\mathrm{2}}\ne b_{\mathrm{2}}$，$c_{\mathrm{1}}\ne c(u)$，$c_{\mathrm{2}}\ne c(u)$。

集合$c_{\mathrm{1}},c_{\mathrm{2}},a_{\mathrm{1}},b_{\mathrm{1}},a_{\mathrm{2}},b_{\mathrm{2}},c(u)$中同种颜色至多出现3次，因此得到的染色为图$G$的一个$k$-frugal $L$-染色，矛盾。

引理4.6.  　设$k$为正整数，$\mathrm{8}\le k\le \mathrm{9}$，则不存在与$k$个$\mathrm{2}$-点相邻的$k$-点。

证明：　这里不妨假设$k=\mathrm{9}$，因为只要$k=\mathrm{9}$成立，$k=\mathrm{8}$的情况类似可证。

设点$v$为一个$\mathrm{9}$-点，且与$\mathrm{9}$个2-点相邻。$N_G\left(v\right)=\{x_{\mathrm{1}},x_{\mathrm{2}},\dots ,x_{\mathrm{9}}\}$，$y_i$为点$x_i$异于点$v$的另一个邻点。由$G$的极小性，图$G-\{v,x_{\mathrm{1}},x_{\mathrm{2}},\dots ,x_{\mathrm{9}}\}$有一个$k$-frugal $L$-染色$c$。

此时点$x_i$被禁用的颜色为$c(y_i)$以及在$N_G(y_i)$中出现$k-\mathrm{1}$次的颜色，点$v$可以染其本身列表中的任意一种颜色。

设点$v$的可用颜色集为$L^{*}\left(v\right)$，点$x_i$的可用颜色集为$L^{*}\left(x_i\right)$（其中$i=\mathrm{1},\mathrm{2},\dots ,\mathrm{9}$），则$\left|L^{*}\left(v\right)\right|=\left|L\left(v\right)\right|\ge \mathrm{1}+\mathrm{3}=\mathrm{4}$，$\left|L^{*}\left(x_i\right)\right|\ge \mathrm{3}$。

下面采用如下方式将这个染色$c$扩充到原图$G$上。

给$x_{\mathrm{1}}$染$c(x_{\mathrm{1}})\in L^{*}\left(x_{\mathrm{1}}\right)$，

给$x_{\mathrm{2}}$染$c(x_{\mathrm{2}})\in L^{*}\left(x_{\mathrm{2}}\right)\backslash \{c(x_{\mathrm{1}})\}$，

给$x_{\mathrm{3}}$染$c\left(x_{\mathrm{3}}\right)\in L^{*}\left(x_{\mathrm{3}}\right)\backslash \{c\left(x_{\mathrm{1}}\right),c(x_{\mathrm{2}})\}$，

给$x_{\mathrm{4}}$染$c(x_{\mathrm{4}})\in L^{*}\left(x_{\mathrm{4}}\right)$，

给$x_{\mathrm{5}}$染$c(x_{\mathrm{5}})\in L^{*}\left(x_{\mathrm{5}}\right)\backslash \{c(x_{\mathrm{4}})\}$，

给$x_{\mathrm{6}}$染$c\left(x_{\mathrm{6}}\right)\in L^{*}\left(x_{\mathrm{6}}\right)\backslash \{c\left(x_{\mathrm{4}}\right),c(x_{\mathrm{5}})\}$，

给$x_{\mathrm{7}}$染$c(x_{\mathrm{7}})\in L^{*}\left(x_{\mathrm{7}}\right)$，

给$x_{\mathrm{8}}$染$c(x_{\mathrm{8}})\in L^{*}\left(x_{\mathrm{8}}\right)\backslash \{c(x_{\mathrm{7}})\}$，

给$x_{\mathrm{9}}$染$c\left(x_{\mathrm{9}}\right)\in L^{*}\left(x_{\mathrm{9}}\right)\backslash \{c\left(x_{\mathrm{7}}\right),c(x_{\mathrm{8}})\}$，

此时，点$x_{\mathrm{1}},x_{\mathrm{2}},x_{\mathrm{3}}$的颜色互不相同，点$x_{\mathrm{4}},x_{\mathrm{5}},x_{\mathrm{6}}$的颜色互不相同，点$x_{\mathrm{7}},x_{\mathrm{8}},x_{\mathrm{9}}$的颜色互不相同。

设$S={\bigcup }_{i=\mathrm{1}}^{\mathrm{9}}\{c(x_i)\}$，则$\mathrm{3}\le |S|\le \mathrm{9}$。

如果$L(v)\backslash S\ne \mathrm{\varnothing }$，给点$v$染$c(v)\in L(v)\backslash S$，就可以把这个染色$c$扩充到图$G$上，矛盾。

下面设$L(v)\subseteq S$，对$k$进行分类讨论。

情况1.  　当$k=\mathrm{4}$时，$\left|L^{*}\left(v\right)\right|=\left|L\left(v\right)\right|=⌈\frac{∆}{k-\mathrm{1}}⌉+\mathrm{3}\ge \mathrm{9}÷\mathrm{3}+\mathrm{3}=\mathrm{6}$。

此时$L(v)$中必然存在3种颜色，这3种颜色在$S$中出现的次数均小于等于1。因为如果只有两种颜色在$S$中出现不超过一次的话，可以推出$S\ge \mathrm{4}\times \mathrm{2}+\mathrm{2}\times \mathrm{1}=\mathrm{10}$，矛盾。

而且，此时必然有$C_{k-\mathrm{1}}\left(v\right)=C_{\mathrm{3}}\left(v\right)\le \mathrm{1}$，因为如果$|C_{k-\mathrm{1}}\left(v\right)|\ge \mathrm{2}$，可以推出$S\ge \mathrm{2}\times \mathrm{3}+\mathrm{4}\times \mathrm{1}=\mathrm{10}$，矛盾。

此时不妨设$c(x_i)\in L(v)\bigcap C_{\mathrm{1}}(v)$，首先擦掉$x_i$的颜色，然后给点$v$染$c(x_i)$，最后用集合$L^{*}\left(x_i\right)\backslash [\{c\left(x_i\right)\}\bigcup C_{\mathrm{3}}\left(v\right)]$中的染色给点$x_i$染色，即可将染色扩充到图$G$上。

情况2.  　当$k\ge \mathrm{5}$时，$\left|L^{*}\left(v\right)\right|=\left|L\left(v\right)\right|=⌈\frac{∆}{k-\mathrm{1}}⌉+\mathrm{3}\ge \mathrm{4}$。

根据前边的染色方法，得知$\forall c\in L(v)$，颜色$c$在集合$S$中出现的次数不超过3，即$C_{\mathrm{4}}\left(v\right)=\mathrm{\varnothing }$。

此时集合$L(v)$中至多有两种颜色在$S$中出现的次数等于3（不妨设这两种颜色为$\{\mathrm{1},\mathrm{2}\}$），因为如果有3种颜色在$S$中出现的次数等于3，则可以推出$\left|S\right|\ge \mathrm{3}\times \mathrm{3}+\mathrm{1}\times \mathrm{1}=\mathrm{10}$，矛盾。

因此，$L(v)$中总有一种颜色，其在$S$中出现的次数小于等于2，不妨设这个颜色为$\{\mathrm{3}\}$。

集合$S$中至多有两个点颜色为$\mathrm{3}$，不妨设为$\{v_i,v_j\}$，首先擦掉这两个点的颜色，给点$v$染颜色3，然后给点$v_i$染集合$L^{*}\left(v_i\right)\backslash \{\mathrm{1},\mathrm{3}\}$中的颜色，给点$v_j$染集合$L^{*}\left(v_j\right)\backslash \{\mathrm{2},\mathrm{3}\}$中的颜色，容易验证此时染色满足5-frugal的条件，因此可以将这个染色扩充到图$G$上。矛盾。

为了方便下列引理的证明，给出几个定义。若一个3-点与3个${\mathrm{4}}^{+}$-点相邻，就称其为重3-点，反之称为轻3-点。若一个8-点与7个2-点和一个重3-点相邻，就称其为轻8-点。

引理4.7.  　不存在与7个$\mathrm{2}$-点和一个轻$\mathrm{3}$-点相邻的$\mathrm{8}$-点。

证明：　假设存在一个$\mathrm{8}$-点$v$，其与7个$\mathrm{2}$-点$x_i$（$i=\mathrm{1},\mathrm{2},\dots ,\mathrm{7}$）和一个轻$\mathrm{3}$-点$x_{\mathrm{8}}$相邻，设$x_i$（$i=\mathrm{1},\mathrm{2},\dots ,\mathrm{7}$）的另一个邻点为$y_i$，$N_G\left(x_{\mathrm{8}}\right)=\{v,y_{\mathrm{8}}^{*},y_{\mathrm{8}}^{**}\}$，其中$y_{\mathrm{8}}^{**}$为${\mathrm{3}}^{-}$-点。由$G$的极小性，图$G-\{v,x_{\mathrm{1}},x_{\mathrm{2}},\dots ,x_{\mathrm{8}}\}$有一个$k$-frugal $L$-染色$c$。

此时，点$x_i$（$i=\mathrm{1},\mathrm{2},\dots ,\mathrm{7}$）被禁用的颜色为$c(y_i)$以及在$N_G(y_i)$中出现$k-\mathrm{1}$次的颜色，点$x_{\mathrm{8}}$被禁用的颜色为$c(y_{\mathrm{8}}^{*})$，$c(y_{\mathrm{8}}^{**})$以及在$N_G(y_{\mathrm{8}}^{*})$中出现$k-\mathrm{1}$次的颜色，点$v$可以染其本身列表中的任意一种颜色。

设点$v$的可用颜色集为$L^{*}\left(v\right)$，点$x_i$的可用颜色集为$L^{*}\left(x_i\right)$，则$\left|L^{*}\left(v\right)\right|=\left|L\left(v\right)\right|=⌈\frac{∆}{k-\mathrm{1}}⌉+\mathrm{3}$，$|L^{*}\left(x_i\right)|\ge \mathrm{3}$ （$i=\mathrm{1},\mathrm{2},\dots ,\mathrm{7}$），$|L^{*}\left(x_{\mathrm{8}}\right)|\ge \mathrm{2}$。

下面将染色$c$扩充到原图$G$上。

给$x_{\mathrm{8}}$染$c(x_{\mathrm{8}})\in L^{*}\left(x_{\mathrm{8}}\right)$，

给$x_{\mathrm{1}}$染$c(x_{\mathrm{1}})\in L^{*}\left(x_{\mathrm{1}}\right)\backslash \{c(x_{\mathrm{8}})\}$，

给$x_{\mathrm{2}}$染$c(x_{\mathrm{2}})\in L^{*}\left(x_{\mathrm{2}}\right)\backslash \{c\left(x_{\mathrm{8}}\right),c(x_{\mathrm{1}})\}$，

给$x_{\mathrm{3}}$染$c(x_{\mathrm{3}})\in L^{*}\left(x_{\mathrm{3}}\right)$，

给$x_{\mathrm{4}}$染$c(x_{\mathrm{4}})\in L^{*}\left(x_{\mathrm{4}}\right)\backslash \{c(x_{\mathrm{3}})\}$，

给$x_{\mathrm{5}}$染$c(x_{\mathrm{5}})\in L^{*}\left(x_{\mathrm{5}}\right)\backslash \{c\left(x_{\mathrm{3}}\right),c(x_{\mathrm{4}})\}$，

给$x_{\mathrm{6}}$染$c(x_{\mathrm{6}})\in L^{*}\left(x_{\mathrm{6}}\right)$，

给$x_{\mathrm{7}}$染$c(x_{\mathrm{7}})\in L^{*}\left(x_{\mathrm{7}}\right)\backslash \{c(x_{\mathrm{6}})\}$，

此时，点$x_{\mathrm{8}},x_{\mathrm{1}},x_{\mathrm{2}}$的颜色互不相同，点$x_{\mathrm{3}},x_{\mathrm{4}},x_{\mathrm{5}}$的颜色互不相同，点$x_{\mathrm{6}},x_{\mathrm{7}}$的颜色互不相同。

设$S={\bigcup }_{i=\mathrm{1}}^{\mathrm{8}}\{c(x_i)\}$，则$\mathrm{3}\le |S|\le \mathrm{8}$。

如果$L(v)\backslash S\ne \mathrm{\varnothing }$，令$c(v)\in L(v)\backslash S$，就可以把这个染色扩充到图$G$上，矛盾。

下面不妨设$L(v)\subseteq S$，对$k$进行分类讨论

情况1.  　当$k=\mathrm{4}$时，$\left|L^{*}\left(v\right)\right|=\left|L\left(v\right)\right|=⌈\frac{∆}{k-\mathrm{1}}⌉+\mathrm{3}\ge \mathrm{3}+\mathrm{3}=\mathrm{6}$从而$|S|\ge L(v)\ge \mathrm{6}$。

此时$L(v)$中必然存在3种颜色，这3种颜色在$S$中出现的次数均小于等于1。因为如果只有两种颜色在$S$中出现不超过一次的话，可以推出$S\ge \mathrm{4}\times \mathrm{2}+\mathrm{2}\times \mathrm{1}=\mathrm{10}$，矛盾。

而且，此时必然有$C_{k-\mathrm{1}}\left(v\right)=C_{\mathrm{3}}\left(v\right)\le \mathrm{1}$，因为如果$|C_{k-\mathrm{1}}\left(v\right)|\ge \mathrm{2}$，可以推出$S\ge \mathrm{2}\times \mathrm{3}+\mathrm{4}\times \mathrm{1}=\mathrm{10}$，矛盾。

此时不妨设$c(x_i)\in L(v)\bigcap C_{\mathrm{1}}(v)$，首先擦掉$x_i$的颜色，然后给点$v$染$c(x_i)$，最后用集合$L^{*}\left(x_i\right)\backslash [\{c\left(x_i\right)\}\bigcup C_{\mathrm{3}}\left(v\right)]$中的染色给点$x_i$染色，即可将染色扩充到图$G$上。

情况2.  　当$k\ge \mathrm{5}$时，$\left|L^{*}\left(v\right)\right|=\left|L\left(v\right)\right|=⌈\frac{∆}{k-\mathrm{1}}⌉+\mathrm{3}\ge \mathrm{4}$，从而$|S|\ge L(v)\ge \mathrm{4}$。

根据前边的染色方法，得知$\forall c\in L(v)$，颜色$c$在集合$S$中出现的次数不超过3，即$C_{\mathrm{4}}\left(v\right)=\mathrm{\varnothing }$。

此时集合$L(v)$中至多有两种颜色在$S$中出现的次数等于3（不妨设这两种颜色为$\{\mathrm{1},\mathrm{2}\}$），因为如果有3种颜色在$S$中出现的次数等于3，则可以推出$\left|S\right|\ge \mathrm{3}\times \mathrm{3}+\mathrm{1}\times \mathrm{1}=\mathrm{10}$，矛盾。

由于$L\left(v\right)\backslash \{\mathrm{1},\mathrm{2},c(x_{\mathrm{8}})\}\ne \mathrm{\varnothing }$，从该集合中任取一个颜色$c_{\mathrm{1}}$，则集合$S$中至多有两个点的颜色为$c_{\mathrm{1}}$，不妨设存在两个点的颜色为$c_{\mathrm{1}}$ （若只有一个点颜色为$c_{\mathrm{1}}$，证明方法类似），且这两个点均不为$x_{\mathrm{8}}$。设这两个点为$\{v_i,v_j\}$。首先擦掉这两个点的颜色，给点$v$染颜色$c_{\mathrm{1}}$，然后给点$v_i$染集合$L^{*}\left(v_i\right)\backslash \{c_{\mathrm{1}},\mathrm{1}\}$中的颜色，给点$v_j$染集合$L^{*}\left(v_j\right)\backslash \{c_{\mathrm{1}},\mathrm{2}\}$中的颜色，容易验证此时染色满足$\mathrm{5}$-frugal的条件，因此可以将这个染色扩充到图$G$上。矛盾。

引理4.8.  　不存在与两个轻$\mathrm{8}$-点相邻的$\mathrm{3}$-点。

证明：　由定义，得知与轻$\mathrm{8}$-点相邻的$\mathrm{3}$-点一定是重$\mathrm{3}$-点。

设$v$为一个重$\mathrm{3}$-点，$u$和$w$为与点$v$相邻的轻$\mathrm{8}$-点，设$N_G\left(u\right)=\{v,x_{\mathrm{1}},x_{\mathrm{2}},\dots ,x_{\mathrm{7}}\}$，$N_G\left(w\right)=\{v,x_{\mathrm{1}}^{*},x_{\mathrm{2}}^{*},\dots ,x_{\mathrm{7}}^{*}\}$。

由$G$的极小性，图$G-\{u,v,w,x_{\mathrm{1}},x_{\mathrm{2}},\dots ,x_{\mathrm{7}},x_{\mathrm{1}}^{*},x_{\mathrm{2}}^{*},\dots ,x_{\mathrm{7}}^{*}\}$有一个$k$-frugal $L$-染色$c$。

设$a\in \{u,v,w,x_{\mathrm{1}},x_{\mathrm{2}},\dots ,x_{\mathrm{7}},x_{\mathrm{1}}^{*},x_{\mathrm{2}}^{*},\dots ,x_{\mathrm{7}}^{*}\}$的可用颜色列表为$L^{*}(a)$，容易得到$|L^{*}\left(v\right)|=|L^{*}\left(x_i\right)|=|L^{*}\left(x_i^{*}\right)|\ge \mathrm{3}$（$i=\mathrm{1},\mathrm{2},\dots ,\mathrm{7}$），$|L^{*}\left(u\right)|=|L\left(u\right)|=⌈\frac{∆}{k-\mathrm{1}}⌉+\mathrm{3}$，$|L^{*}\left(w\right)|=|L\left(w\right)|=⌈\frac{∆}{k-\mathrm{1}}⌉+\mathrm{3}$。（方法类似上述引理，在此不再赘述。）

设$L^{*}\left(v\right)=\{a,b,c\}$，分别取$L_{\mathrm{1}}^{*}(v)=\{a,b\}$，$L_{\mathrm{2}}^{*}(v)=\{a,c\}$，$L_{\mathrm{3}}^{*}(v)=\{b,c\}$，观察点$u,v,x_{\mathrm{1}},x_{\mathrm{2}},\dots ,x_{\mathrm{7}}$，由引理4.7的证明过程，得知，如果一个$\mathrm{8}$-点的列表长度为$⌈\frac{∆}{k-\mathrm{1}}⌉+\mathrm{3}$， 8个邻点中有7个点的列表长度为3，有一个点的列表长度为2，那么总可以从其列表中选取适当的颜色，使得这个染色为正常的。因此基于上述点$v$的三种不同的列表，可以得到3种关于这8 个点的染色方案，分别记作$c_x,c_y,c_z$。

上述3种染色方案中点$v$使用的列表均不完全相同，因此$c_x(v)$，$c_y(v)$，$c_z(v)$这3种颜色不可能完全相同，所以总可以找到两个方案，不妨设为$c_x,c_y$，满足$c_x(v)\ne c_y(v)$，这里不妨设$c_x\left(v\right)=a$，$c_y\left(v\right)=b$。

令$L_{\mathrm{4}}^{*}(v)=\{a,b\}$，观察点$v,w,x_{\mathrm{1}}^{*},x_{\mathrm{2}}^{*},\dots ,x_{\mathrm{7}}^{*}$，由引理4.7，可以得到关于这8个点的染色方案，记作$c_{\mathrm{0}}$。

此时，如果$c_{\mathrm{0}}\left(v\right)=a$，就用方案$c_x$给点$u,v,x_{\mathrm{1}},x_{\mathrm{2}},\dots ,x_{\mathrm{7}}$染色，用方案$c_{\mathrm{0}}$给点$v,w,x_{\mathrm{1}}^{*},x_{\mathrm{2}}^{*},\dots ,x_{\mathrm{7}}^{*}$染色。

如果$c_{\mathrm{0}}\left(v\right)=b$，就用方案$c_y$给点$u,v,x_{\mathrm{1}},x_{\mathrm{2}},\dots ,x_{\mathrm{7}}$染色，用方案点$c_{\mathrm{0}}$给点$v,w,x_{\mathrm{1}}^{*},x_{\mathrm{2}}^{*},\dots ,x_{\mathrm{7}}^{*}$染色。

容易验证此时得到的染色为原图的一个$k$-frugal $L$-染色，因此可以将染色$c$扩充到图$G$上，矛盾。

这样就通过discharging的方法来获得一个矛盾，首先给每个点$v$赋初始权$\omega \left(v\right)=d(v)$，设权转移后得到的新权为${\omega }^{*}\left(v\right)$。

下面给出权转移规则：

（R1）每个点均向相邻的$\mathrm{2}$-点转移$\frac{\mathrm{2}}{\mathrm{3}}$。

（R2）除了轻$\mathrm{8}$-点外，每个${\mathrm{4}}^{+}$-点向相邻的$\mathrm{3}$-点转移$\frac{\mathrm{1}}{\mathrm{6}}$。

下边来验证上述过程，每个点的权均大于等于$\frac{\mathrm{10}}{\mathrm{3}}$。

设点$v$为一个$k$-点，因为图$G$中没有$\mathrm{1}$-点，所以$k\ge \mathrm{2}$。

如果$k=\mathrm{2}$，由（R1）容易验证${\omega }^{*}\left(v\right)=\mathrm{2}+\frac{\mathrm{2}}{\mathrm{3}}=\frac{\mathrm{10}}{\mathrm{3}}$。

如果$k=\mathrm{3}$，分两种情况讨论。

若$v$不与轻$\mathrm{8}$-点相邻，由引理4.4，$v$周围至少有两个${\mathrm{4}}^{+}$-点，由（R2），容易验证${\omega }^{*}\left(v\right)=\mathrm{3}+\frac{\mathrm{1}}{\mathrm{6}}\times \mathrm{2}=\frac{\mathrm{10}}{\mathrm{3}}$。若$v$与轻$\mathrm{8}$-点相邻，由引理4.7和引理4.8，点$v$必然为重$\mathrm{3}$-点，且点$v$周围至多有一个轻$\mathrm{8}$-点，因此除了这个轻$\mathrm{8}$-点，点$v$周围还存在两个${\mathrm{4}}^{+}$-点，由（R2），容易验证${\omega }^{*}\left(v\right)=\mathrm{3}+\frac{\mathrm{1}}{\mathrm{6}}\times \mathrm{2}=\frac{\mathrm{10}}{\mathrm{3}}$。

如果$\mathrm{4}\le k\le \mathrm{6}$，由引理4.3，点$v$周围不存在$\mathrm{2}$-点，由（R2）容易验证${\omega }^{*}\left(v\right)\ge \mathrm{d}\left(v\right)-\frac{\mathrm{1}}{\mathrm{6}}\mathrm{d}\left(v\right)=\frac{\mathrm{5}}{\mathrm{6}}\mathrm{d}(v)\ge \frac{\mathrm{10}}{\mathrm{3}}$。

如果$k=\mathrm{7}$，由引理4.5，点$v$周围至多存在5个$\mathrm{2}$-点，由（R1）（R2），容易验证${\omega }^{*}\left(v\right)\ge \mathrm{7}-\frac{\mathrm{2}}{\mathrm{3}}\times \mathrm{5}-\frac{\mathrm{1}}{\mathrm{6}}\times \mathrm{2}=\frac{\mathrm{10}}{\mathrm{3}}$。

如果$k=\mathrm{8}$，由引理4.6，点$v$周围至多存在7个$\mathrm{2}$-点，下面分两种情况讨论。

若点$v$为轻$\mathrm{8}$-点，由引理4.8，如果点$v$与7个$\mathrm{2}$-点和1个$\mathrm{3}$-点相邻，则这个$\mathrm{3}$-点必定为重$\mathrm{3}$-点，由（R2）可得轻$\mathrm{8}$-点不需要给相邻的$\mathrm{3}$-点转移权，容易验证${\omega }^{*}\left(v\right)\ge \mathrm{8}-\frac{\mathrm{2}}{\mathrm{3}}\times \mathrm{7}=\frac{\mathrm{10}}{\mathrm{3}}$。若点$v$不为轻$\mathrm{8}$-点，由（R2），容易验证${\omega }^{*}\left(v\right)\ge \mathrm{8}-\frac{\mathrm{2}}{\mathrm{3}}\times \mathrm{7}=\frac{\mathrm{10}}{\mathrm{3}}$。

如果$k=\mathrm{9}$，由引理3.6，点$v$周围至多存在8个$\mathrm{2}$-点，容易验证${\omega }^{*}\left(v\right)\ge \mathrm{9}-\frac{\mathrm{2}}{\mathrm{3}}\times \mathrm{8}-\frac{\mathrm{1}}{\mathrm{6}}=\mathrm{3.5}>\frac{\mathrm{10}}{\mathrm{3}}$。

如果$k\ge \mathrm{10}$，容易验证${\omega }^{*}\left(v\right)\ge d\left(v\right)-\frac{\mathrm{2}}{\mathrm{3}}d\left(v\right)=\frac{\mathrm{1}}{\mathrm{3}}d(v)\ge \frac{\mathrm{10}}{\mathrm{3}}$。

这样就得到一个矛盾，定理得证。

作者贡献声明

房启明：提出研究问题，设计研究方案，起草论文；

张莉：对发表文章作最后的审阅和定稿，并在研究的过程中提出诸多启发性观点。