本文所考虑的图均为简单无向图. 设$ G=(V, E) $是一个简单连通图, 其中$ V(G) $表示图G的顶点集, $ E(G) $表示图G的边集. 对于$ \forall v \in V(G) $, 用$ d(v) $表示顶点v的度, 其中度为1的点称为悬挂点, $ \Delta(G)=\max\{d(v)|v\in V(G)\} $为图G的最大度, 简记为$ \Delta $. 本文中使用但未定义的术语和符号见参考文献[1].

图的染色问题是近年来图论研究的热点问题, 其具有重要的理论意义和广泛的实用背景. 2004年, 张忠辅等在文[2]中提出了图的邻点可区别全染色的概念, 即图G的一个k-邻点可区别全染色是一个满足相邻点色集合不同的正常全染色f (即, 从$ : V(G)\cup E(G)\rightarrow \{1, 2, \cdots, k\} $的映射), 其中任意一点的色集合为该点及关联边上的所染颜色构成的集合, 称$ \chi_{at}(G)=\min\{k|G $存在一个k- 邻点可区别全染色为G的邻点可区别全色数. 随后, 图的邻点可区别全染色引起了国内外学者的广泛关注, 见参考文献[3–8, 11–13]等. 2007年, 张忠辅等在文[9]中提出了图的邻点强可区别全染色, 并给出了路、圈、完全二部图和树的邻点强可区别全色数.下面给出图的邻点强可区别全染色的概念:

定义1.1^[9]   令$ G=(V, E) $是一个$ |V(G)|\geq3 $的简单连通图, f是一个从$ E(G)\cup V(G) $到$ \{1, 2, \ldots, k\} $的映射, 其中k是一个正整数. 若满足

$ (1) $对任意边$ uv\in E(G) $, $ f(u)\neq f(v), f(u)\neq f(uv), f(v)\neq f(uv) $;

$ (2) $对任意相邻边$ uv, uw\in E(G)(v\neq w) $, $ f(uv)\neq f(uw) $;

$ (3) $对任意边$ uv\in E(G) $, $ C_{f}\langle u\rangle \neq C_{f}\langle v\rangle $.

其中$ C_{f}\langle u\rangle=\{f(u)\}\cup\{f(uv), f(v)|uv\in E(G)\} $. 则f被称为G的一个邻点强可区别全染色, 简记为G的$ k-AVSDTC $, 图G满足邻点强可区别全染色的最小颜色数k称为邻点强可区别全色数, 简记$ \chi_{ast}(G) $. 显然

$ \chi_{ast}(G)=\min\{k|G\mbox{存在一个}k-AVSDTC\}. $

基于一些特殊图类如路、圈、完全二部图和树的邻点强可区别全染色研究, 张忠辅等^[9]猜想:

猜想1.2 ^[9]   对于阶数不小于3的平面图G, 则有$ \chi_{ast}(G)\leq\Delta(G)+3 $.

一个简单连通图G满足$ k=|E(G)|-|V(G)|+1 $时被称为k-圈图. 特别地, 当$ k=1 $时称为单圈图, 记作U; 当$ k=2 $时称为双圈图, 将不包含悬挂点的双圈图称为双圈基图. 根据双圈图的结构, 可将其分为三类: $ \theta $-图, $ \infty $-图和哑铃图, 其分别对应于图 1中的$ B_{1}(r, s, t)(r, s, t $中至少有两个大于等于$ 1) $, $ B_{2}(r, t)(r\geq2, t\geq2) $和$ B_{3}(r, s, t)(r\geq2, t\geq2) $, 见文献[10]. 其中要特别说明的是: 在$ B_{1}(r, s, t) $中, 如果$ r, s, t $中任意一个数为0时, 意味着点x与点y相邻; 在$ B_{3}(r, s, t) $中, 如果$ s=0 $时, 意味着点x与点y相邻.

本文主要考虑了双圈图的邻点强可区别全染色, 并得到了如下结论:

定理1.3   设图G是一个双圈图. 若G以$ \infty $-图为基图的双圈图, 则$ \chi_{ast}(G)\leq\Delta(G)+2 $; 其他$ \chi_{ast}(G)\leq\Delta(G)+3 $.

通过上述结论, 进一步验证了猜想1.2在双圈图上是成立的.

引理2.1^[9]   对于顶点数$ |V(G)|\geq3 $的图G, 有$ \chi_{ast}(G)\geq\Delta+1 $. 特别地, 如果G含有两个相邻的最大度顶点, 则$ \chi_{ast}(G)\geq\Delta+2 $.

引理2.2^[9]   令$ C_{n} $是阶数为n的圈, 则

$ \chi_{ast}(C_{n})=\left\{ \begin{aligned} 4&, \ n\neq 4, 10 且n是偶数;\\ 5&, \ \mbox{其他}.\\ \end{aligned} \right. $

由引理2.2知, $ \chi_{ast}(C_{n})\leq\Delta(C_{n})+3 $, 故猜想1.2成立.

引理2.3   对于任意图G, 设x是图G中的一个顶点, 并且记$ d(x)=d $, 令点y是点x的邻点. 假设f是图G的一个正常全染色. 如果$ d(y)\leq\lfloor\frac{d-1}{2}\rfloor $或者$ d(y)\geq2d+1 $, 则有$ C_{f}\langle x\rangle\neq C_{f}\langle y\rangle $.

证    显然, 对任意$ x\in V(G) $都有$ d+1\le |C_{f}\langle x\rangle|\le 2d+1 $. 若$ d(y)\leq\lfloor\frac{d-1}{2}\rfloor $, 则有$ |C_{f}\langle y\rangle|\le 2d(y)+1\le d<d+1\le |C_{f}\langle x\rangle| $; 若$ d(y)\geq2d+1 $, 类似可证$ |C_{f}\langle y\rangle|>|C_{f}\langle x\rangle| $. 因此, $ C_{f}\langle x\rangle\neq C_{f}\langle y\rangle $, 结论成立.

在图G的正常全染色f下, 若悬挂点x的邻点为y, 且$ d(y)\geq3 $, 则由引理2.3可知, x与其的邻点y的色集合是强可区分的. 因而有如下推论:

推论2.4   设x是图G的一个悬挂点, y是x的邻点, 若$ d(y)\geq3 $, 则$ C_{f}\langle x\rangle $ $ \neq C_{f}\langle y\rangle $.

证   设图G是$ \Delta(G)\geq3 $的双圈图, H是以$ \infty $-图为基图的双圈图. 记色集合为$ C=\{1, 2, \ldots, \Delta(G)+2\} $. 首先, 根据图G是否同构于H分为以下两种情形:

情形1   $ G\cong H $.

当$ G\cong H $时, 由$ B_{2}(r, t) $知$ \Delta(G)\geq4 $, 则$ \Delta(G)+2\geq6 $. 根据G是否有悬挂点分为两种子情形:

情形1.1   图G没有悬挂点.

利用拆分和粘合的方法分析其结构, 如图 2所示.

将图G拆分为图$ G_{1} $和图$ G_{2} $, 显然图$ G_{1} $和图$ G_{2} $都是圈. 由引理2.2知, 图$ G_{1} $和图$ G_{2} $均是5色可染的, 假设所用的5种色为$ \{1, 2, 3, 4, 5\} $. 不失一般性, 用颜色1染图$ G_{1} $和图$ G_{2} $中的点x, 用颜色2染图$ G_{1} $中的边$ u_{1}x $, 用颜色3染图$ G_{1} $中的边$ u_{r}x $, 用颜色4染图$ G_{2} $中的边$ xw_{1} $, 用颜色5染图$ G_{2} $中的边$ xw_{t} $, 为了保证以上染色能做到, 可以在图$ G_{1} $和图$ G_{2} $中进行颜色轮换, 使得上述染色成立. 现将图$ G_{1} $和图$ G_{2} $粘合变成图G. 此时, 会得到$ C_{f}\langle x\rangle=\{1, 2, 3, 4, 5\} $. 考虑最坏的情况, 即$ C_{f}\langle u_{1}\rangle=C_{f}\langle u_{r}\rangle=C_{f}\langle w_{1}\rangle=C_{f}\langle w_{t}\rangle=C_{f}\langle x\rangle=\{1, 2, 3, 4, 5\} $. 则用颜色$ g\in\{C\setminus\{1, 2, 3, 4, 5\}\} $中的任一种颜色重染点$ w_{1} $. 于是, $ C_{f}\langle x\rangle=\{1, 2, 3, 4, 5, g\} $, 即$ |C_{f}\langle x\rangle|=6 $, 而$ |C_{f}\langle u_{1}\rangle|=|C_{f}\langle u_{r}\rangle|=|C_{f}\langle w_{1}\rangle|=|C_{f}\langle w_{t}\rangle|=5 $, 所以粘合后的点x与其邻点均是可区别的, 故该情形得证.

情形1.2   图G至少有一个悬挂点.

根据悬挂点的邻点是否在基图上又可以分为以下两种情形:

情形1.2.1   悬挂点的邻点都在基图上.

不失一般性, 设任意一个悬挂点$ \omega $的邻点为$ u_{i} $, 显然$ d(u_{i})\geq3 $, 记点$ u_{i} $除点$ \omega $之外的其余邻点为$ u_{i-1}, u_{i+1}, t_{1}, \ldots, t_{d(u_{i})-3} $, 其中$ 2\leq d(u_{j})\leq\Delta $, $ j=i-1, i+1 $. $ d(t_{i})=1 $, $ i=1, 2, \ldots, d(u_{i})-3 $. 见图 3(a). 利用第二数学归纳法来证明该情形. 首先删去一个悬挂点$ \omega $. 令$ G^{'}=G-\omega $, 由归纳假设, $ \chi_{ast}(G^{'})\leq\Delta(G^{'})+2 $, 其中$ \Delta(G^{'})\leq \Delta(G) $. 令$ f^{'} $是$ G^{'} $的$ (\Delta(G^{'})+2)-AVSDTC $. 现在将$ f^{'} $拓展为G的一个$ (\Delta(G)+2)-AVSDTC $ f. 令$ f^{'}(u_{i})=1, f^{'}(u_{i}t_{j})=j+1, j=1, 2, \ldots, d(u_{i})-3, f^{'}(u_{i}u_{i+1})=d(u_{i})-1, f^{'}(u_{i}u_{i-1})=d(u_{i}) $, 则$ |C_{f^{'}}\langle u_{i}\rangle|\geq d(u_{i}) $. 由推论2.4知, $ C_{f}\langle u_{i}\rangle\neq C_{f}\langle t_{j}\rangle, j=1, 2, \ldots, d(u_{i})-3 $.

如果$ |C_{f^{'}}\langle u_{i}\rangle|\geq d(u_{i})+1 $, 则用$ C_{f^{'}}\langle u_{i}\rangle\setminus\{1, 2, \ldots, d(u_{i})\} $中的任一种颜色染给边$ u_{i}\omega $, 点$ \omega $染颜色2. 此时, $ C_{f^{'}}\langle u_{i}\rangle=C_{f}\langle u_{i}\rangle $. 因此, 得到$ C_{f}\langle u_{i}\rangle\neq C_{f}\langle u_{i-1}\rangle $且$ C_{f}\langle u_{i}\rangle\neq C_{f}\langle u_{i+1}\rangle $.

如果$ |C_{f^{'}}\langle u_{i}\rangle|=d(u_{i}) $, 则$ C_{f^{'}}\langle u_{i}\rangle=\{1, 2, \ldots, d(u_{i})\} $. 首先f是一个正常的全染色, 所以$ f(u_{i}\omega)\neq f(u_{i}) $, $ f(u_{i}\omega)\neq f(u_{i}t_{j}), j=1, 2, \ldots, d(u_{i})-3 $, $ f(u_{i}\omega)\neq f(u_{i}u_{i-1}) $且$ f(u_{i}\omega)\neq f(u_{i}u_{i+1}) $. 故$ u_{i}\omega $有$ d(u_{i}) $种禁用色; 同理点$ u_{1} $有2种禁用色. 因此, 边$ u_{i}\omega $和点$ \omega $有$ (C-d(u_{i}))\times(C-2)\geq2\Delta $种可用色组合.

首先考虑点$ u_{i} $与点$ u_{i-1} $的色集合的可区分性. 显然当$ |C_{f^{'}}\langle u_{i-1}\rangle|-|C_{f^{'}}\langle u_{i}\rangle|\geq3 $或$ |C_{f^{'}}\langle u_{i-1}\rangle| $ $ -|C_{f^{'}}\langle u_{i}\rangle|\leq0 $时, $ C_{f}\langle u_{i}\rangle\neq C_{f}\langle u_{i-1}\rangle $.

$ (1) $如果$ |C_{f^{'}}\langle u_{i-1}\rangle|-|C_{f^{'}}\langle u_{i}\rangle|=2 $, 不失一般性, 假设$ C_{f^{'}}\langle u_{i-1}\rangle=\{1, 2, \ldots, d(u_{i}), x, y\} $. 则当边$ u_{i}\omega $和点$ \omega $是$ (x, y) $或$ (y, x) $时会导致$ C_{f}\langle u_{i}\rangle=C_{f}\langle u_{i-1}\rangle $. 因此, 边$ u_{i}\omega $和点$ \omega $存在至多2种禁用色组合使得$ C_{f}\langle u_{i}\rangle=C_{f}\langle u_{i-1}\rangle $;

$ (2) $如果$ |C_{f^{'}}\langle u_{i-1}\rangle|-|C_{f^{'}}\langle u_{i}\rangle|=1 $, 不失一般性, 假设$ C_{f^{'}}\langle u_{i-1}\rangle=\{1, 2, \ldots, d(u_{i}), x\} $. 则当边$ u_{i}\omega $和点$ \omega $是$ (x, j), j=2, 3, \ldots, d(u_{i}) $中的一种时, 会导致$ C_{f}\langle u_{i}\rangle=C_{f}\langle u_{i-1}\rangle $. 因此, 至多有$ d(u_{i})-1 $种禁用色组合使得点$ u_{i} $与点$ u_{i-1} $的色集合不可区分.

根据(1)和(2), 至多有$ \max\{2, d(u_{i})-1\}=d(u_{i})-1 $种禁用色组合使得$ C_{f}\langle u_{i}\rangle=C_{f}\langle u_{i-1}\rangle $. 同理, 至多有$ d(u_{i})-1 $种禁用色组合使得$ C_{f}\langle u_{i}\rangle=C_{f}\langle u_{i+1}\rangle $. 于是, 边$ u_{i}\omega $和点$ \omega $至少有$ 2\Delta-2(d(u_{i})-1)\geq2 $种可用色组合. 对于G的其他元素, 保持$ f=f' $(在后面的证明中不在赘述). 因此, G有一个$ (\Delta(G)+2)-AVSDTC $ f.

情形1.2.2   至少有一个悬挂点的邻点不在基图上.

选择一个距离基图最远的悬挂点, 记作点$ \omega $, 点$ \omega $的邻点记为t, 则$ 2\leq d(t)\leq\Delta $. 将t的除去点$ \omega $的邻点记为$ t_{i} $, $ i=1, 2, \ldots, d(t)-1 $, 其中$ 2\leq t_{1}\leq\Delta $, $ t_{j}=1 $, $ j=2, 3, \ldots, d(t)-1 $, 见图 3(b). 显然可得$ |C_{f}\langle t\rangle|\geq3 $, $ |C_{f}\langle t_{1}\rangle|\geq3 $. 令$ G^{'}=G-\omega $, 由归纳假设, $ \chi_{ast}(G^{'})\leq\Delta(G^{'})+2 $, 其中$ \Delta(G^{'})\leq \Delta(G) $. 令$ f^{'} $是$ G^{'} $的$ (\Delta(G^{'})+2)-AVSDTC $. 下面按照点t的度分为两种情形:

$ (1) $当$ d(t)=2 $. 若$ 3\leq|C_{f}\langle t_{1}\rangle|\leq5 $, 则令$ f(t\omega)\subset C\setminus C_{f}\langle t_{1}\rangle $, $ f(\omega)=2 $; 若$ |C_{f}\langle t_{1}\rangle|\geq6 $, 则令$ f(t\omega)\subset C_{f}\langle t_{1}\rangle\setminus \{f^{'}(t), f^{'}(t\omega), f^{'}(\omega)\} $, $ f(\omega)=2 $.

$ (2) $当$ d(t)\geq3 $. 由推论2.4知, $ C_{f}\langle t\rangle\neq C_{f}\langle t_{j}\rangle, j=2, 3, \ldots, d(t)-1 $. 考虑到边$ t\omega $有$ d(t) $种禁用色, 点$ \omega $有2种禁用色, 故边$ t\omega $和点$ \omega $共有$ (C-d(t))(C-2)\geq2\Delta $种可用组合. 证明过程类似情形1.2.1中的(1)和(2). 故至多有$ \max\{2, d(t)-1\}=d(t)-1 $种禁用色组合使得$ C_{f}\langle u_{i}\rangle=C_{f}\langle u_{i-1}\rangle $. 同理, 至多有$ d(t)-1 $种禁用色组合使得$ C_{f}\langle t\rangle=C_{f}\langle t_{1}\rangle $. 于是, 边$ t\omega $和点$ \omega $至少有$ 2\Delta-2(d(t)-1)\geq2 $种可用色组合.

这与G的选取矛盾. 因此, G存在一个$ (\Delta(G)+2)-AVSDTC $ f.

情形2   $ G\not \cong H $.

当$ G\not \cong H $时, $ \Delta(G)\geq3 $, 从而$ \Delta(G)+3\geq6 $. 根据图G是否有悬挂点分为两种子情形:

情形2.1   图G没有悬挂点.

当图G没有悬挂点时, 又可以将图G分为以下两种情形:

情形2.1.1   图G同构于以$ \theta- $图为基图的双圈图.

$ (1) $当$ B_{1}(r, s, t) $中的$ r, s, t\leq2 $时, 染色方案如图 4所示.

$ (2) $当$ r, s, t $中至少有一个大于等于3时, 利用数学归纳法来证明该情形. 不失一般性, 设$ r\geq3 $, 如图 5所示. 令$ G^{'}=G-u_{i} $, $ 2\leq i\leq r-1 $, 需要说明的是: 如果$ i=2 $, 则点$ u_{i-2} $与点x重合; 如果$ i=r-1 $, 则点$ u_{i+2} $与点y重合. 由归纳假设知$ G^{'} $有一个$ (\Delta(G^{'})+2)-AVSDTC $ $ f^{'} $, 其色集合记为$ C=\{1, 2, \ldots, \Delta(G^{'})+2\} $. 下面染边$ u_{i-1}u_{i} $, $ u_{i}u_{i+1} $和点$ u_{i} $, 将$ f^{'} $拓展为G的一个AVSDTC f. 根据点$ u_{i-1} $和点$ u_{i+1} $在$ G^{'} $中的颜色是否相同, 考虑以下两种情形:

$ (2.1) $$ f^{'}(u_{i-1})=f^{'}(u_{i+1}) $.

不失一般性, 假设$ f^{'}(u_{i-1})=f^{'}(u_{i+1})=1 $, $ f^{'}(u_{i-2}u_{i-1})=a $和$ f^{'}(u_{i+1}u_{i+2}) $ $ =b $. 由定义1.1知f首先是G的一个正常的全染色. 因此, 边$ u_{i-1}u_{i} $有2种禁用色, 即$ f(u_{i-1}u_{i})\neq f(u_{i-2}u_{i-1}) $且$ f(u_{i-1}u_{i})\neq f(u_{i-1}) $, 其中$ f(u_{i-2}u_{i-1}) $ $ =f^{'}(u_{i-2}u_{i-1}) $且$ f(u_{i-1})=f^{'}(u_{i-1}) $; 边$ u_{i}u_{i+1} $有3种禁用色, 即$ f(u_{i}u_{i+1})\neq f(u_{i-1}u_{i}) $, $ f(u_{i}u_{i+1})\neq f(u_{i+1}) $且$ f(u_{i}u_{i+1})\neq f(u_{i+1}u_{i+2}) $, 其中$ f(u_{i+1})=f^{'}(u_{i+1})) $, $ f(u_{i+1}u_{i+2})= f^{'} $ $ (u_{i+1}u_{i+2})) $; 点$ u_{i} $有3种禁用色, 即$ f(u_{i})\neq f(u_{i-1}) $, $ f(u_{i})\neq f(u_{i-1}u_{i}) $且$ f(u_{i})\neq f(u_{i}u_{i+1}) $. 因此, 边$ u_{i-1}u_{i} $, 边$ u_{i}u_{i+1} $和点$ u_{i} $至少有$ (6-2)\times(6-3)\times(6-3)=36 $种可用色组合. 下面考虑会使点$ u_{i-2} $和点$ u_{i-1} $的色集合相同的禁用色组合数. 显然, 当$ |C_{f^{'}}\langle u_{i-2}\rangle|-|C_{f^{'}}\langle u_{i-1}\rangle|\geq3 $或$ |C_{f^{'}}\langle u_{i-2}\rangle|-|C_{f^{'}}\langle u_{i-1}\rangle|\leq0 $时, $ C_{f}\langle u_{i-2}\rangle\neq C_{f}\langle u_{i-1}\rangle $.

$ a) $如果$ |C_{f^{'}}\langle u_{i-2}\rangle|-|C_{f^{'}}\langle u_{i-1}\rangle|=2 $, 则边$ u_{i-1}u_{i} $和点$ u_{i} $至多存在2种禁用色组合, 即$ \{f(u_{i-1} $ $ u_{i}), f(u_{i})\}\subset C_{f^{'}}\langle u_{i-2}\rangle\setminus C_{f^{'}}\langle u_{i-1}\rangle $使得$ C_{f}\langle u_{i-2}\rangle $ $ =C_{f}\langle u_{i-1}\rangle $. 注意到边$ u_{i}u_{i+1} $有3种可用色, 因此至多有$ 2\times3=6 $种禁用色组合使得点$ u_{i-2} $与点$ u_{i-1} $的色集合不可区分;

$ b) $如果$ |C_{f^{'}}\langle u_{i-2}\rangle|-|C_{f^{'}}\langle u_{i-1}\rangle|=1 $, 则边$ u_{i-1}u_{i} $和点$ u_{i} $至多存在3种禁用色组合使得$ C_{f}\langle u_{i-2}\rangle=C_{f}\langle u_{i-1}\rangle $. 尽可能使禁用色组合的数量最大化, 假设$ f^{'}(u_{i-2})=c $, $ C_{f^{'}}\langle u_{i-1}\rangle=\{1, a, c\} $且$ C_{f^{'}}\langle u_{i-2}\rangle=\{1, a, c, d\} $, 其中$ 1, a, c $和d彼此互不相同. 当边$ u_{i-1}u_{i} $和点$ u_{i} $上的颜色是$ (c, d) $, $ (d, c) $和$ (d, a) $这三种组合中的一种时, 会导致$ C_{f}\langle u_{i-2}\rangle=C_{f}\langle u_{i-1}\rangle $. 注意到边$ u_{i}u_{i+1} $有3种可用色. 因此, 至多有$ 3\times3=9 $种禁用色组合使得点$ u_{i-2} $和点$ u_{i-1} $的色集合不可区分.

由a)和b)得知, 至多有$ \max \{6, 9\}=9 $种禁用色组合使得$ C_{f}\langle u_{i-2}\rangle=C_{f}\langle u_{i-1}\rangle $. 计算结果受染色先后顺序影响, 所以边$ u_{i}u_{i+1} $和点$ u_{i} $至多有3种禁用色组合使得$ C_{f}\langle u_{i+2}\rangle=C_{f}\langle u_{i+1}\rangle $. 注意到边$ u_{i-1}u_{i} $有4种可用色. 因此, 至多有$ 3\times4=12 $种禁用色组合使得$ C_{f}\langle u_{i+2}\rangle=C_{f}\langle u_{i+1}\rangle $.

下面考虑会导致点$ u_{i-1} $和点$ u_{i} $的色集合相同的禁用色组合数. 假设边$ u_{i-1}u_{i} $和点$ u_{i} $已在f下被着色, 则$ 3\leq|C_{f}\langle u_{i-1}\rangle|\leq5 $.

$ ⅰ) $如果$ |C_{f}\langle u_{i-1}\rangle|=3 $, 不失一般性, 假设$ C_{f}\langle u_{i-1}\rangle=\{1, a, c\} $, 则有$ f^{'}(u_{i-2}) $ $ =f(u_{i-2})=f(u_{i-1}u_{i})=c $和$ f(u_{i})=a $. 因为$ f(u_{i+1})=1 $, 所以$ f(u_{i}u_{i+1}) $ $ \neq1 $. 注意到$ f(u_{i}u_{i+1})\neq a $和$ f(u_{i}u_{i+1})\neq c $, 所以$ f(u_{i}u_{i+1})\notin C_{f}\langle u_{i-1}\rangle $. 因此, $ C_{f}\langle u_{i-1}\rangle\neq C_{f}\langle u_{i}\rangle $;

$ ⅱ) $如果$ |C_{f}\langle u_{i-1}\rangle|=4 $, 则边$ u_{i-1}u_{i} $, 点$ u_{i} $和边$ u_{i}u_{i+1} $至多存在4种禁用色组合使得$ C_{f}\langle u_{i-1}\rangle=C_{f}\langle u_{i}\rangle $. 为了讨论最坏的情况, 即保证禁用组合数最多, 假设$ C_{f}\langle u_{i-1}\rangle=\{1, a, c, d\} $. 当边$ u_{i-1}u_{i} $, 点$ u_{i} $和边$ u_{i}u_{i+1} $上的颜色是依次是$ (c, a, d) $, $ (c, d, a) $, $ (d, a, c) $和$ (d, c, a) $中的一种时, 会导致$ C_{f}\langle u_{i-1}\rangle=C_{f}\langle u_{i}\rangle $. 因此, 至多有4种禁用色组合使得点$ u_{i-1} $和点$ u_{i} $的色集合不可区分;

$ ⅲ) $如果$ |C_{f}\langle u_{i-1}\rangle|=5 $, 则$ C_{f}\langle u_{i-1}\rangle\neq C_{f}\langle u_{i}\rangle $. 是因为$ f(u_{i-1})=f(u_{i+1})=1 $, 显然有$ |C_{f}\langle u_{i}\rangle|=4 $.

根据ⅰ), ⅱ)和ⅲ), 至多有4种禁用色组合会导致$ C_{f}\langle u_{i-1}\rangle=C_{f}\langle u_{i}\rangle $. 同理, 至多有4种禁用色组合会导致$ C_{f}\langle u_{i+1}\rangle=C_{f}\langle u_{i}\rangle $. 于是, 边$ u_{i-1}u_{i} $, 边$ u_{i}u_{i+1} $和点$ u_{i} $至少有$ 36-9-12-4\times2=7 $种可用色组合. 因此, 可以将$ f^{'} $扩展为G的一个$ (\Delta(G)+2)-AVSDTC $ f.

(2.2) $ f^{'}(u_{i-1})\neq f^{'}(u_{i+1}) $.

不失一般性, 假设$ f^{'}(u_{i-1})=1 $, $ f^{'}(u_{i+1})=2 $, $ f^{'}(u_{i-2}u_{i-1})=a $和$ f^{'}(u_{i+1}u_{i+2}) $ $ =b $. 为了使禁用色组合的数量尽可能多, 设$ a, b\neq1, 2 $. 由定义1.1知f首先应该是G的一个正常全染色. 因此, 点$ u_{i} $有2种禁用色, 即$ f(u_{i})\neq f(u_{i-1}) $, $ f(u_{i})\neq f(u_{i+1}) $; 边$ u_{i-1}u_{i} $有3种禁用色; 边$ u_{i}u_{i+1} $有4种禁用色. 所以, 点$ u_{i} $, 边$ u_{i-1}u_{i} $和$ u_{i}u_{i+1} $至少有$ (6-2)\times(6-3)\times(6-4)=24 $种可用色组合.

首先, 考虑使得点$ u_{i-2} $与点$ u_{i-1} $的色集合相同的禁用色组合数. 显然, 当$ |C_{f^{'}}\langle u_{i-2}\rangle|-|C_{f^{'}}\langle u_{i-1}\rangle|\geq3 $或$ |C_{f^{'}}\langle u_{i-2}\rangle|-|C_{f^{'}}\langle u_{i-1}\rangle|\leq0 $时, $ C_{f}\langle u_{i-2}\rangle\neq C_{f}\langle u_{i-1}\rangle $.

$ a) $如果$ |C_{f^{'}}\langle u_{i-2}\rangle|-|C_{f^{'}}\langle u_{i-1}\rangle|=2 $, 则至多存在2种禁用色组合$ \{f(u_{i-1}u_{i}), $ $ f(u_{i})\}\subset C_{f^{'}}\langle u_{i-2}\rangle\setminus C_{f^{'}}\langle u_{i-1}\rangle $使得$ C_{f}\langle u_{i-2}\rangle=C_{f}\langle u_{i-1}\rangle $. 又由于边$ u_{i}u_{i+1} $有2种可用色, 故至多有$ 2\times2=4 $种禁用色组合使得点$ u_{i-2} $和点$ u_{i-1} $的色集合不可区分;

$ b) $如果$ |C_{f^{'}}\langle u_{i-2}\rangle|-|C_{f^{'}}\langle u_{i-1}\rangle|=1 $, 则至多有3种禁用色组合使得$ C_{f}\langle u_{i-2}\rangle $ $ =C_{f}\langle u_{i-1}\rangle $. 不失一般性, 设$ f^{'}(u_{i-2})=c $, $ C_{f^{'}}\langle u_{i-1}\rangle=\{1, a, c\} $且$ C_{f^{'}}\langle u_{i-2}\rangle $ $ =\{1, a, c, d\} $. 当边$ u_{i-1}u_{i} $和点$ u_{i} $为$ (c, d) $, $ (d, c) $和$ (d, a) $中的一种组合时, 会导致$ C_{f}\langle u_{i-2}\rangle=C_{f}\langle u_{i-1}\rangle $. 又由于$ u_{i}u_{i+1} $有2种可用色. 于是, 至多有$ 3\times2=6 $种禁用色组合使得点$ u_{i-2} $和点$ u_{i-1} $的色集合不可区分.

根据a)和b), 至多有$ \max\{4, 6\}=6 $种禁用色组合使得$ C_{f}\langle u_{i-2}\rangle=C_{f}\langle u_{i-1}\rangle $. 类似地, 点$ u_{i+2} $和点$ u_{i+1} $至多有9种禁用色组合使得$ C_{f}\langle u_{i+2}\rangle=C_{f}\langle u_{i+1}\rangle $.下面考虑会使得点$ u_{i-1} $和点$ u_{i} $的色集合相同的禁用色组合数. 假设边$ u_{i-1}u_{i} $和点$ u_{i} $已在f下被着色, 则$ 3\leq|C_{f}\langle u_{i-1}\rangle|\leq5 $.

$ ⅰ) $如果$ |C_{f}\langle u_{i-1}\rangle|=3 $, 则边$ u_{i-1}u_{i} $, 点$ u_{i} $和边$ u_{i}u_{i+1} $至多有1种禁用色组合, 即$ (2, a, 1) $. 因为$ f^{'}(u_{i+1})=2 $, 所以$ 2\in C_{f}\langle u_{i}\rangle $. 为了确保$ C_{f}\langle u_{i-1}\rangle $ $ =C_{f}\langle u_{i}\rangle $, 则$ f(u_{i-1}u_{i})=2 $, 进一步得$ f(u_{i})=f^{'}(u_{i-2}u_{i-1})=a $且$ f(u_{i} $ $ u_{i+1})=f^{'}(u_{i-1})=1 $. 因此, 至多有1种禁用色组合使得点$ u_{i-1} $和点$ u_{i} $的色集合不可区分;

$ ⅱ) $如果$ |C_{f}\langle u_{i-1}\rangle|=4 $, 则至多存在3种禁用色组合使得$ C_{f}\langle u_{i-1}\rangle=C_{f}\langle u_{i}\rangle $. 由$ f^{'}(u_{i+1})=2 $得$ 2\in C_{f}\langle u_{i-1}\rangle $. 不失一般性, 令$ C_{f}\langle u_{i-1}\rangle=\{1, 2, a, c\} $. 当边$ u_{i-1}u_{i} $, 点$ u_{i} $和边$ u_{i}u_{i+1} $为$ (c, a, 1) $, $ (2, c, a) $和$ (2, $ $ a, c) $中的组合之一时会导致$ C_{f}\langle u_{i-1}\rangle=C_{f}\langle u_{i}\rangle $. 因此, 至多存在3种禁用色组合使得点$ u_{i-1} $和点$ u_{i} $的色集合不可区分;

$ ⅲ) $如果$ |C_{f}\langle u_{i-1}\rangle|=5 $, 不失有一般性, 假设$ C_{f}\langle u_{i-1}\rangle=\{1, 2, a, c, d\} $. 当边$ u_{i-1}u_{i} $, 点$ u_{i} $和边$ u_{i}u_{i+1} $为$ (c, d, a) $和$ (d, c, a) $中的一种时会导致$ C_{f}\langle u_{i-1}\rangle $ $ =C_{f}\langle u_{i}\rangle $. 因此, 至多有2种禁用色组合使得点$ u_{i-1} $和点$ u_{i} $的色集合不可区分.

根据ⅰ), ⅱ)和ⅲ), 至多有3种禁用色组合使得$ C_{f}\langle u_{i-1}\rangle=C_{f}\langle u_{i}\rangle $. 类似地, 至多有3种禁用色组合使得$ C_{f}\langle u_{i+1}\rangle=C_{f}\langle u_{i}\rangle $. 于是, 边$ u_{i-1}u_{i} $, 点$ u_{i} $和边$ u_{i}u_{i+1} $至少有$ 24-6-9-3\times2=3 $种可用色组合. 因此, 可以将$ f^{'} $扩展为G的一个$ (\Delta(G)+2)-AVSDTC $ f.

情形2.1.2   图G同构于以哑铃图为基图的双圈图.

$ (1) $当$ B_{3}(r, s, t) $中的$ s=0 $时, 如图 6所示, 将图G拆分为图$ G_{1} $和图$ G_{2} $, 显然图$ G_{1} $和图$ G_{2} $都是单圈图. 容易知道, 图$ G_{1} $和图$ G_{2} $均5色可染的, 假设所用的5种色为$ \{1, 2, 3, 4, 5\} $. 不失一般性, 首先用颜色1染图$ G_{1} $中的点x和图$ G_{2} $中的点y, 其次用颜色2染图$ G_{1} $和图$ G_{2} $中的边xy, 接着用颜色3染图$ G_{1} $中的y和图$ G_{2} $中的点x, 最后将图$ G_{2} $中颜色1和3进行轮换. 将图$ G_{1} $和图$ G_{2} $粘合变成图G. 此时, 用颜色$ g\in C\setminus\{1, 2, 3, 4, 5\} $中的任一种颜色重染边$ yw_{1} $. 显然粘合后各点之间的色集合均可区别, 故该情形得证.

$ (2) $当$ B_{3}(r, s, t) $中的$ s\geq1 $时, 如图 7所示, 将图G拆分为图$ G_{1} $和图$ G_{2} $, 显然图$ G_{1} $和图$ G_{2} $都是单圈图. 容易推知, 图$ G_{1} $和图$ G_{2} $均是5色可染的, 不妨设所用的5种色为$ \{1, 2, 3, 4, 5\} $. 不失一般性, 首先用颜色1染图$ G_{1} $和图$ G_{2} $中的点$ v_{k} $, 其次用颜色2染图$ G_{1} $中边$ v_{k-1}v_{k} $和图$ G_{2} $中的边$ v_{k}v_{k+1} $, 接着用颜色3染图$ G_{1} $中的点$ v_{k-1} $和图$ G_{2} $中的点$ v_{k+1} $, 最后将图$ G_{2} $中颜色2和4进行轮换, 颜色3和5进行轮换. 将图$ G_{1} $和图$ G_{2} $粘合变成图G. 此时, $ C_{f}\langle v_{k}\rangle=\{1, 2, 3, 4, 5\} $. 为了避免点$ v_{k} $和其邻点的色集合重复, 于是用颜色$ g\in C\setminus\{1, 2, 3, 4, 5\} $中的任一种颜色重染点$ v_{k-1} $和边$ v_{k}v_{k+1} $. 此时各点之间均可区别, 该情形得证.

情形2.2   图G至少含有一个悬挂点.

证明过程类似情形1.2, 这里不再赘述.