最大度为6的图<i>G</i>的邻点可区别边色数的一个上界


扩展功能
	加入收藏夹

	复制引文信息

	加入引用管理器

	Email Alert

	RSS
本文作者相关文章
	吴燕青

最大度为6的图G的邻点可区别边色数的一个上界

吴燕青

山西师范大学数学与计算机科学学院, 山西临汾 041000

收稿日期：2017-06-26; 接收日期：2017-10-18

作者简介：吴燕青(1982-), 男, 山西大同, 讲师, 主要研究方向:图论及其应用.

摘要：本文研究了最大度为6的图G的邻点可区别边着色问题.利用反证法，得到了最大度为6的非半正则图G的邻点可区别边色数的一个上界.

关键词：最大度邻点可区别边着色邻点可区别边色数

AN UPPER BOUND ON ADJACENT VERTEX-DISTINGUISHING CHROMATIC INDEX OF GRAPHS WITH MAXIMUM DEGREE SIX

WU Yan-qing

School of Mathematics and Computer Science, Shanxi Normal University, Linfen 041000, China

Abstract: In this paper, we discuss the problem of the adjacent vertex distinguishing edge coloring on the graph with maximum degree six. By using reduction to absurdity, an upper bound on the adjacent vertex distinguishing chromatic index for the graph G which is not a semi-regular graph with maximum degree six is obtained.

Keywords: maximum degree adjacent vertex distinguishing edge coloring adjacent vertex distinguishing chromatic index

1 引言

本文主要考虑不含孤立边的有限简单图.对图$ G $, 用$ V(G) $, $ E(G) $, $ \Delta(G) $和$ {\rm mad}(G) $分别表示图$ G $的顶点集, 边集, 最大度和最大平均度.在$ G $中, 用$ N_{G}(v) $表示顶点$ v $的邻集.度为$ k $的顶点称为$ k $ -顶点.度至少为(至多为) $ k $的顶点称为$ k^{+} $ -顶点($ k^{-} $ -顶点).用$ d_{i}(v) $表示与顶点$ v $相邻的$ i $ -顶点的数目.一个图$ G $称为半正则的, 如果它的每一条边至少和一个最大度顶点相关联.否则, 称为非半正则的.一个图$ G $的正常边着色是一个映射$ \phi $: $ E(G)\rightarrow \{1, \cdots, k\} $, 使得每一对相邻边$ e_{1} $和$ e_{2} $, 有$ \phi(e_{1})\neq\phi (e_{2}) $.用$ c_{\phi}(v) $表示在着色$ \phi $下与$ v $相关联的边所着的颜色组成的集合.一个图$ G $的正常边着色$ \phi $称为邻点可区别边着色, 如果$ G $的任何相邻顶点$ u $和$ v $, 满足$ c_{\phi}(u)\neq c_{\phi}(v) $. $ G $的邻点可区别边色数$ \chi'_{a}(G) $是使得$ G $有一个$ k $ -邻点可区别边着色的最少颜色数$ k $.

在$ 2002 $年, 文献[1]首先讨论了邻点可区别边着色问题, 并提出了以下猜想.

猜想设图$ G $为顶点数至少为3的连通图且$ G\neq G_{5} $, 则$ \chi'_{a}(G)\leq \Delta+2 $.

对于一般图$ G $, 文献[2]给出了若$ \Delta(G)>10^{20} $, 则$ \chi'_{a}(G)\leq\Delta(G)+300 $.文献[3]给出了$ \chi'_{a}(G)\leq3\Delta(G) $.文献[4]给出了$ \chi'_{a}(G)\leq2.5\Delta(G)+5 $.文献[5]给出了若$ \Delta(G)\leq3 $, 则$ \chi'_{a}(G)\leq 5 $.文献[6]给出了若$ \Delta(G)\leq5 $且$ {\rm mad}(G)<3-\frac{2}{\Delta(G)} $, 则$ \chi'_{a}(G)\leq \Delta(G)+1 $.文献[7]给出了若$ \Delta(G)\leq4 $, 则$ \chi'_{a}(G)\leq 8 $, 和若$ \Delta(G)\leq5 $, 则$ \chi'_{a}(G)\leq 10 $.本文证明了若$ G $是一个最大度为6的非半正则图, 则$ \chi'_{a}(G)\leq12 $.

引理1.1^[7] 假设$ G $是一个$ \Delta(G)\geq2 $的半正则图.若$ \Delta(G)\equiv0\; ({\rm mod}\; 3) $, 则$ \chi'_{a}(G)\leq \frac{5}{3}\Delta(G)+3. $

2 主要结果

定理2.1 设$ G $是一个最大度为6的非半正则图, 则$ \chi'_{a}(G)\leq12 $.

证假设$ G $是含边数最少的连通的极小反例.由于$ G $是非半正则的, 所以存在$ uv\in E(G) $, 使得$ d_{G}(u)\leq5 $且$ d_{G}(v)\leq5 $.不妨设$ d_{H}(u)\leq d_{H}(v) $.设$ H = G-uv $, 由$ G $的极小性可知, $ H $有一个12 -邻点可区别边着色$ \phi $, 它用的颜色集$ C = \{1, 2, \cdots, 12\} $.为了叙述起来方便, 称在$ \phi $下边$ e $对颜色$ \alpha $是允许的, 若在$ \phi $下用颜色$ \alpha $给边$ e $重新着色可得$ H $的一个新的12 -邻点可区别边着色.用$ L(e) $表示在$ \phi $下由边$ e $的所有允许的颜色组成的集.设$ xy\in E(H) $, 且$ d_{G}(x) = d_{G}(y) $.若颜色$ \beta\in c_{\phi}(y)\backslash c_{\phi}(x) $, 且$ |c_{\phi}(y)\cap c_{\phi}(x)| = d_{H}(x) = d_{H}(y)-1 $, 则称在$ \phi $下颜色$ \beta $为顶点$ x $的不法颜色.用$ A_{x} $表示在$ \phi $下顶点$ x $的所有不法颜色组成的集.设$ \Omega_{z}(x) = \{c_{\phi}(y)|y\in N_{H}(x)\backslash\{z\}\} $ (或$ \Omega(x) = \{c_{\phi}(y)|y\in N_{H}(x)\} $).由$ uv $的选择可知$ d_{H}(u)+d_{H}(v)\leq 8 $.

情形1 假设$ d_{H}(u)+d_{H}(v)\leq6 $.

情形1.1 假设$ d_{H}(u) = 0 $.由$ uv $的选择和$ G $的假设可知$ 1\leq d_{H}(v)\leq4 $.显然, 存在$ p\in C\backslash c_{\phi}(v) $, 用$ p $给$ uv $着色可得$ G $的一个$ 12 $ -邻点可区别边着色, 矛盾.

情形1.2 假设$ d_{H}(u) = 1 $且$ u'\in N_{H}(u) $.由$ uv $的选择可知$ 1\leq d_{H}(v)\leq4 $.

假设$ d_{H}(v) = 1 $且$ v'\in N_{H}(v) $.若$ \phi(vv')\neq \phi(uu') $, 显然, 存在$ p\in C\backslash \{c_{\phi}(v)\cup c_{\phi}(u)\} $, 用$ p $给$ uv $着色可得$ G $的一个$ 12 $ -邻点可区别边着色, 矛盾.否则, $ \phi(vv') = \phi(uu') $.由于$ |L(vv')|\geq1 $, 所以存在$ q\in L(vv') $.现用$ q $给$ vv' $重新着色可得$ H $的一个$ 12 $ -邻点可区别边着色$ \phi' $.从而$ \phi'(vv')\neq \phi'(uu') $, 正如前面已讨论, 矛盾.

假设$ 2\leq d_{H}(v)\leq 4 $.显然, 存在$ p\in C\backslash \{c_{\phi}(v)\cup c_{\phi}(u)\} $, 用$ p $给$ uv $着色可得$ G $的一个$ 12 $ -邻点可区别边着色, 矛盾.

情形1.3 假设$ d_{H}(u) = 2 $且$ u_{j}\in N_{H}(u) $, 其中$ j = 1, 2 $.由$ uv $的选择可知$ 2\leq d_{H}(v)\leq4 $.

假设$ d_{H}(v) = 2 $且$ v_{j}\in N_{H}(v) $, 其中$ j = 1, 2 $.若$ |c_{\phi}(u)\cap c_{\phi}(v)|\leq1 $, 显然, 存在$ p\in C\backslash \{c_{\phi}(v)\cup c_{\phi}(u)\} $, 用$ p $给$ uv $着色可得$ G $的一个$ 12 $ -邻点可区别边着色, 矛盾.否则, $ |c_{\phi}(u)\cap c_{\phi}(v)| = 2 $.不妨设$ \phi(vv_{1}) = 1 $和$ \phi(vv_{2}) = 2 $.在$ H $中, 若$ v $的邻点有一个$ 5^{-} $ -顶点, 不妨设$ d_{H}(v_{1})\leq5 $.由于$ |L(vv_{1})|\geq1 $, 所以存在$ p\in L(vv_{1}) $.现用$ p $给$ vv_{1} $重新着色可得$ H $的一个$ 12 $ -邻点可区别边着色$ \phi' $.从而$ |c_{\phi'}(u)\cap c_{\phi'}(v)| = 1 $, 正如前面已讨论, 矛盾.否则, $ v_{1} $和$ v_{2} $均是$ 6 $ -顶点.设$ v_{1j}\in N_{H}(v_{1}) $, 其中$ j = 1, 2, 3, 4, 5 $.若$ 2\in c_{\phi}(v_{1}) $, 因而$ |L(vv_{1})|\geq1 $, 所以存在$ p\in L(vv_{1}) $.现用$ p $给$ vv_{1} $重新着色可得$ H $的一个$ 12 $ -邻点可区别边着色$ \phi' $.从而$ |c_{\phi'}(u)\cap c_{\phi'}(v)| = 1 $, 正如前面已讨论, 矛盾.否则, $ 2\notin c_{\phi}(v_{1}) $.不妨设$ \phi(v_{1}v_{1j}) = j+2 $, 其中$ j = 1, 2, 3, 4, 5 $.若存在$ q\in C\backslash \{c_{\phi}(v)\cup c_{\phi}(v_{1})\} $, 用$ q $给$ vv_{1} $重新着色可得$ H $的一个$ 12 $ -邻点可区别边着色$ \phi' $, 从而$ |c_{\phi'}(u)\cap c_{\phi'}(v)| = 1 $, 正如前面已讨论, 矛盾.否则, 不妨设$ c_{\phi}(v_{11}) = \{3, 4, 5, 6, 7, 8\} $, $ c_{\phi}(v_{12}) = \{3, 4, 5, 6, $ $ 7, 9\} $, $ c_{\phi}(v_{13}) = \{3, 4, 5, 6, 7, 10\} $, $ c_{\phi}(v_{14}) = \{3, 4, 5, 6, 7, 11\} $和$ c_{\phi}(v _{15}) = \{3, 4, 5, 6, 7, 12\} $.若存在$ r\in\{1, 2\} $, 使得$ \{r, 4, 5, 6, 7, 8\}\notin \Omega_{v_{1}}(v_{11}) $, 那么用$ r $和$ 3 $分别给$ v_{1}v_{11} $和$ vv_{1} $重新着色可得$ H $的一个$ 12 $ -邻点可区别边着色$ \phi' $.从而$ |c_{\phi'}(u)\cap c_{\phi'}(v)| = 1 $, 正如前面已讨论, 矛盾.否则, 在$ \phi $下, $ \{\{1, 4, 5, 6, 7, 8\}, $ $ \{2, 4, 5, 6, 7, 8\}\}\subseteq \Omega_{v_{1}}(v_{11}) $.由于$ |\Omega_{v_{1}}(v_{11})| = 5 $, 所以存在$ s\in\{9, 10, 11, 12\} $, 使得$ \{s, 4, 5, 6, 7, 8\}\notin \Omega_{v_{1}}(v_{11}) $.现用$ s $和$ t\in\{9, 10, 11, 12\}\backslash\{s\} $, 分别给$ v_{1}v_{11} $和$ vv_{1} $重新着色可得$ H $的一个$ 12 $ -邻点可区别边着色$ \phi' $.从而$ |c_{\phi'}(u)\cap c_{\phi'}(v)| = 1 $, 正如前面已讨论, 矛盾.

假设$ 3\leq d_{H}(v)\leq4 $.由前面的讨论可知, $ u_{j} $均是$ 4^{+} $ -顶点, 其中$ j = 1, 2 $.显然, 存在$ p\in C\backslash \{c_{\phi}(v)\cup c_{\phi}(u)\} $, 用$ p $给$ uv $着色可得$ G $的一个$ 12 $ -邻点可区别边着色, 矛盾.

情形1.4 假设$ d_{H}(u) = 3 $.因而$ d_{H}(v) = 3 $.设$ v_{j}\in N_{H}(v) $, 其中$ j = 1, 2, 3 $.

假设$ |c_{\phi}(u)\cap c_{\phi}(v)| = 0 $.若存在$ p\in C\backslash \{c_{\phi}(v)\cup c_{\phi}(u)\} $, 用$ p $给$ uv $着色可得$ G $的一个$ 12 $ -邻点可区别边着色, 矛盾.否则, 在$ \phi $下, $ \{\{p\}\cup c_{\phi}(v)\}\in \Omega(v) $, 或$ \{\{p\}\cup c_{\phi}(u)\}\in \Omega(u) $.由于$ |L(vv_{1})|\geq5 $, 所以存在$ q\in L(vv_{1})\backslash \{c_{\phi}(v_{2})\cup c_{\phi}(v_{3})\} $.现用$ q $给$ vv_{1} $重新着色, 用$ \phi(vv_{1}) $给$ uv $着色可得$ G $的一个$ 12 $ -邻点可区别边着色, 矛盾.

假设$ 1\leq|c_{\phi}(u)\cap c_{\phi}(v)|\leq2 $.显然, 存在$ p\in C\backslash \{c_{\phi}(v)\cup c_{\phi}(u)\} $, 用$ p $给$ uv $着色可得$ G $的一个$ 12 $ -邻点可区别边着色, 矛盾.

假设$ |c_{\phi}(u)\cap c_{\phi}(v)| = 3 $.不妨设$ \phi(vv_{j}) = j $, 其中$ j = 1, 2, 3 $.

在$ H $中, 假设$ v $的邻点中有一个$ 5^{-} $ -顶点.不妨设$ d(v_{1})\leq5 $.由情形$ 1.3 $可知, $ v_{2} $和$ v_{3} $均不是$ 3 $ -顶点.显然, $ |L(vv_{1})|\geq1 $, 所以存在$ p\in L(vv_{1}) $, 用$ p $给$ vv_{1} $重新着色可得$ H $的一个$ 12 $ -邻点可区别边着色$ \phi' $.从而$ |c_{\phi'}(u)\cap c_{\phi'}(v)| = 2 $, 正如前面已讨论, 矛盾.

在$ H $中, 假设$ v $的邻点均是$ 6 $ -顶点.设$ v_{1j}\in N_{H}(v_{1}) $, 其中$ j = 1, 2, 3, 4, 5 $.

假设$ |\{2, 3\}\cap c_{\phi}(v_{1})| = 0 $.不妨设$ \phi(v_{1}v_{1j}) = j+3 $, 其中$ j = 1, 2, 3, 4, 5 $.若存在$ p\in C\backslash \{c_{\phi}(v)\cup c_{\phi}(v_{1})\} $, 用$ p $给$ vv_{1} $重新着色可得$ H $的一个$ 12 $ -邻点可区别边着色$ \phi' $, 从而$ |c_{\phi'}(u)\cap c_{\phi'}(v)| = 2 $, 正如前面已讨论, 矛盾.否则, 不妨设$ c_{\phi}(v_{11}) = \{4, 5, 6, 7, 8, 9\} $, $ c_{\phi}(v_{12}) = \{4, 5, 6, $ $ 7, 8, 10\} $, $ c_{\phi}(v_{13}) = \{4, 5, 6, 7, 8, 11\} $和$ c_{\phi}(v_{14}) = \{4, 5, 6, 7, 8, 12\} $.若存在$ q\in\{1, 2, 3\} $, 使得$ \{q, 5, $ $ 6, 7, 8, 9\}\notin \Omega_{v_{1}}(v_{11}) $, 那么先用$ q $给$ v_{1}v_{11} $重新着色.进一步, 若用$ 4 $给$ vv_{1} $重新着色可得$ H $的一个$ 12 $ -邻点可区别边着色, 从而$ |c_{\phi'}(u)\cap c_{\phi'}(v)| = 2 $, 正如前面已讨论, 矛盾.否则, $ c_{\phi}(v_{15}) = \{q, 4, 5, 6, 7, 8\} $.现用$ 10 $给$ vv_{1} $重新着色可得$ H $的一个$ 12 $ -邻点可区别边着色$ \phi'' $.从而$ |c_{\phi''}(u)\cap c_{\phi''}(v)| = 2 $, 正如前面已讨论, 矛盾.否则, 在$ \phi $下, $ \{\{1, 5, 6, 7, 8, 9\}, $ $ \{2, 5, 6, 7, 8, 9\}, \{3, 5, 6, 7, 8, $ $ 9\}\}\subseteq\Omega_{v_{1}}(v_{11}) $.由于$ |\Omega_{v_{1}}(v_{11})| = 5 $, 所以存在$ r\in\{10, 11, 12\} $, 使得$ \{r, 5, 6, 7, 8, 9\}\notin \Omega_{v_{1}}(v_{11}) $.若用$ r $和$ s\in\{10, 11, 12\}\backslash\{r\} $分别给$ v_{1}v_{11} $和$ vv_{1} $重新着色可得$ H $的一个$ 12 $ -邻点可区别边着色$ \phi' $, 从而$ |c_{\phi'}(u)\cap c_{\phi'}(v)| = 2 $, 正如前面已讨论, 矛盾.否则, $ c_{\phi}(v_{5}) = \{r, s, 5, 6, 7, 8\} $.现用$ r $和$ t\in\{10, 11, 12\}\backslash\{r, s\} $分别给$ v_{1}v_{11} $和$ vv_{1} $重新着色可得$ H $的一个$ 12 $ -邻点可区别边着色$ \phi'' $.从而$ |c_{\phi''}(u) $ $ \cap c_{\phi''}(v)| = 2 $, 正如前面已讨论, 矛盾.

假设$ |\{2, 3\}\cap c_{\phi}(v_{1})| = 1 $.不妨设$ \phi(v_{1}v_{11}) = 2 $, $ \phi(v_{1}v_{1j}) = j+2 $, 其中$ j = 2, 3, 4, 5 $.若存在$ p\in C\backslash \{c_{\phi}(v)\cup c_{\phi}(v_{1})\} $, 用$ p $给$ vv_{1} $重新着色可得$ H $的一个$ 12 $ -邻点可区别边着色$ \phi' $, 从而$ |c_{\phi'}(u)\cap c_{\phi'}(v)| = 2 $, 正如前面已讨论, 矛盾.否则, 不妨设$ c_{\phi}(v_{11}) = \{2, 4, 5, 6, 7, 8\} $, $ c_{\phi}(v_{12}) = \{2, 4, 5, 6, 7, 9\} $, $ c_{\phi}(v_{13}) = \{2, 4, 5, 6, 7, 10\} $, $ c_{\phi}(v_{14}) = \{2, 4, 5, 6, 7, 11\} $和$ c_{\phi}(v_{15}) = \{2, 4, 5, 6, 7, 12\} $.若存在$ q\in\{1, 3\} $, 使得$ \{q, 2, 5, 6, 7, 9\}\notin \Omega_{v_{1}}(v_{12}) $, 那么用$ q $和$ 4 $分别给$ v_{1}v_{12} $和$ vv_{1} $重新着色可得$ H $的一个$ 12 $ -邻点可区别边着色$ \phi' $.从而$ |c_{\phi'}(u)\cap c_{\phi'}(v)| = 2 $, 正如前面已讨论, 矛盾.否则, 在$ \phi $下, $ \{\{1, 2, 5, 6, 7, 9\}, \{2, 3, 5, 6, 7, 9\}\}\subseteq\Omega_{v_{1}}(v_{12}) $.由于$ |\Omega_{v_{1}}(v_{12})| = 5 $, 所以存在$ r\in\{8, 10, 11, 12\} $, 使得$ \{r, 2, 5, 6, 7, 9\}\notin \Omega_{v_{1}}(v_{12}) $.现用$ r $和$ s\in\{8, 10, 11, 12\}\backslash\{r\} $分别给$ v_{1}v_{12} $和$ vv_{1} $重新着色可得$ H $的一个$ 12 $ -邻点可区别边着色$ \phi' $.从而$ |c_{\phi'}(u) $ $ \cap c_{\phi'}(v)| = 2 $, 正如前面已讨论, 矛盾.

假设$ |\{2, 3\}\cap c_{\phi}(v_{1})| = 2 $.由于$ |L(vv_{1})|\geq1 $, 所以存在$ p\in L(vv_{1}) $.现用$ p $给$ vv_{1} $重新着色可得$ H $的一个$ 12 $ -邻点可区别边着色$ \phi' $, 从而$ |c_{\phi'}(u)\cap c_{\phi'}(v)| = 2 $, 正如前面已讨论, 矛盾.

情形2 假设$ d_{H}(u)+d_{H}(v) = 7 $.由$ uv $的选择可知$ d_{H}(u) = 3 $且$ d_{H}(v) = 4 $.设$ u_{j}\in N_{H}(u) $, 其中$ j = 1, 2, 3 $.由情形$ 1 $可知, $ u_{j} $均为$ 5^{+} $ -顶点, 其中$ j = 1, 2, 3 $.因此存在$ p\in C\backslash\{c_{\phi}(u)\cup c_{\phi}(v)\} $, 用$ p $给$ uv $着色可得$ G $的一个$ 12 $ -邻点可区别边着色, 矛盾.

情形3 假设$ d_{H}(u)+d_{H}(v) = 8 $.由$ uv $的选择可知$ d_{H}(u) = 4 $且$ d_{H}(v) = 4 $.设$ v_{i}\in N_{H}(v) $, 其中$ i = 1, 2, 3, 4 $.在$ \phi $下, 不妨设$ \phi(vv_{i}) = i $, 其中$ i = 1, 2, 3, 4 $.设$ u_{j}\in N_{H}(u) $, 其中$ j = 1, 2, 3, 4 $.由情形$ 1 $和$ 2 $可知, 在$ H $中, 与$ u $相邻的顶点和与$ v $相邻的顶点均是$ 5^{+} $ -顶点.

情形3.1 假设$ d_{H}(u_{j}) = 6 $, 其中$ j = 1, 2, 3, 4 $.

情形3.1.1 假设$ |c_{\phi}(u)\cap c_{\phi}(v)| = 0 $.设$ \phi(uu_{j}) = j+4 $, 其中$ j = 1, 2, 3, 4 $.若存在$ p\in C\backslash\{c_{\phi}(u)\cup c_{\phi}(v)\} $, 用$ p $给$ uv $着色可得$ G $的一个$ 12 $ -邻点可区别边着色, 矛盾.否则, 在$ \phi $下, $ \{\{p\}\cup c_{\phi}(v)\}\in \Omega(v) $.显然, $ C\backslash \{c_{\phi}(v)\cup c_{\phi}(u)\} = \{9, 10, 11, 12\} $.不妨设$ c_{\phi}(v_{1}) = \{1, 2, 3, 4, 9\} $, $ c_{\phi}(v_{2}) = \{1, 2, 3, 4, 10\} $, $ c_{\phi}(v_{3}) = \{1, 2, 3, 4, 11\} $和$ c_{\phi}(v_{4}) = \{1, 2, 3, 4, 12\} $.若存在$ q\in \{5, 6, 7, 8\} $, 使得$ \{q, 2, 3, 4, 9\}\notin \Omega_{v}(v_{1}) $, 那么用$ q $给$ vv_{1} $重新着色, 用$ 1 $给$ uv $着色可得$ G $的一个$ 12 $ -邻点可区别边着色, 矛盾.否则, 在$ \phi $下, $ \Omega_{v}(v_{1}) = \{\{2, 3, 4, $ $ 5, 9\}, \{2, 3, 4, 6, 9\}, \{2, 3, 4, 7, 9\}, \{2, 3, 4, 8, 9\}\} $.现用$ 10 $给$ vv_{1} $重新着色, 用$ 11 $给$ uv $着色可得$ G $的一个$ 12 $ -邻点可区别边着色, 矛盾.

情形3.1.2 假设$ 1\leq|c_{\phi}(u)\cap c_{\phi}(v)|\leq3 $.显然, 存在$ p\in C\backslash \{c_{\phi}(u)\cup c_{\phi}(v)\} $, 用$ p $给$ uv $着色可得$ G $的一个$ 12 $ -邻点可区别边着色, 矛盾.

情形3.1.3 假设$ |c_{\phi}(u)\cap c_{\phi}(v)| = 4 $.

在$ H $中, 假设$ d_{6}(v) = 4 $.因此$ d(v_{i}) = 6 $, 其中$ i = 1, 2, 3, 4 $.设$ v_{1j}\in N_{H}(v_{1})\backslash \{v\} $, 其中$ j = 1, 2, 3, 4, 5 $.

假设$ |\{2, 3, 4\}\cap c_{\phi}(v_{1})| = 0 $.不妨设$ \phi(v_{1}v_{1j}) = j+4 $, 其中$ j = 1, 2, 3, 4, 5 $.若存在$ p\in C\backslash \{c_{\phi}(v)\cup c_{\phi}(v_{1})\} $, 用$ p $给$ vv_{1} $重新着色可得$ H $的一个$ 12 $ -邻点可区别边着色$ \phi' $, 从而$ |c_{\phi'}(u)\cap c_{\phi'}(v)| = 3 $, 正如情形$ 3.1.2 $, 矛盾.否则, 不妨设$ c_{\phi}(v_{11}) = \{5, 6, 7, 8, 9, 10\} $, $ c_{\phi}(v_{12}) = \{5, 6, 7, 8, 9, $ $ 11\} $和$ c_{\phi}(v_{13}) $ $ = \{5, 6, 7, 8, 9, 12\} $.若存在$ q\in \{1, 2, 3, 4\} $, 使得$ \{q, 6, 7, 8, 9, 10\}\notin \Omega_{v_{1}}(v_{11}) $, 那么先用$ q $给$ v_{1}v_{11} $重新着色.进一步, 若用$ 5 $给$ vv_{1} $重新着色可得$ H $的一个$ 12 $ -邻点可区别边着色$ \phi' $, 从而$ |c_{\phi'}(u)\cap c_{\phi'}(v)| = 3 $, 正如情形$ 3.1.2 $, 矛盾.否则, $ c_{\phi}(v_{14}) = \{q, 5, 6, 7, 8, 9\} $, 或$ c_{\phi}(v_{15}) = \{q, 5, 6, 7, 8, 9\} $.不妨设$ c_{\phi}(v_{14}) = \{q, 5, 6, 7, 8, 9\} $.若用$ 11 $给$ vv_{1} $重新着色可得$ H $的一个$ 12 $ -邻点可区别边着色$ \phi'' $, 从而$ |c_{\phi''}(u)\cap c_{\phi''}(v)| = 3 $, 正如情形$ 3.1.2 $, 矛盾.否则, $ c_{\phi}(v_{15}) = \{q, 6, 7, 8, 9, $ $ 11\} $.现用$ 12 $给$ vv_{1} $重新着色可得$ H $的一个$ 12 $ -邻点可区别边着色$ \phi''' $.从而$ |c_{\phi'''}(u)\cap c_{\phi'''}(v)| = 3 $, 正如情形$ 3.1.2 $, 矛盾.否则, 在$ \phi $下, $ \{\{1, 6, 7, 8, 9, 10\}, \{2, 6, 7, 8, 9, 10\}, $ $ \{3, 6, 7, 8, 9, 10\}, \{4, 6, 7, 8, $ $ 9, 10\}\} $ $ \subseteq \Omega_{v_{1}}(v_{11}) $.类似的, $ \{\{1, 5, 7, 8, 9, 11\}, \{2, 5, 7, 8, 9, 11\}, $ $ \{3, 5, 7, 8, 9, 11\}, \{4, 5, 7, 8, 9, 11\}\}\subseteq \Omega_{v_{1}}(v_{12}) $.由于$ |\Omega_{v_{1}}(v_{1j})| = 5 $, 其中$ j = 1, 2 $, 所以存在$ r\in \{11, 12\} $, 不妨设$ r = 11 $, 使得$ \{6, 7, 8, 9, 10, 11\}\notin \Omega_{v_{1}}(v_{11}) $, 存在$ s\in\{10, 12\} $, 使得$ \{s, 5, 7, 8, 9, 11\}\notin \Omega_{v_{1}}(v_{12}) $.若用$ 11 $和$ 12 $分别给$ v_{1}v_{11} $和$ vv_{1} $重新着色可得$ H $的一个$ 12 $ -邻点可区别边着色$ \phi' $, 从而$ |c_{\phi'}(u)\cap c_{\phi'}(v)| = 3 $, 正如情形$ 3.1.2 $, 矛盾.否则, $ c_{\phi}(v_{14}) = \{6, 7, 8, 9, 11, 12\} $, 或$ c_{\phi}(v_{15}) = \{6, 7, 8, 9, 11, 12\} $.不妨设$ c_{\phi}(v_{14}) = \{6, 7, 8, 9, $ $ 11, 12\} $.若用$ s $和$ t\in\{10, 12\}\backslash\{s\} $分别给$ v_{1}v_{12} $和$ vv_{1} $重新着色可得$ H $的一个$ 12 $ -邻点可区别边着色$ \phi'' $, 从而$ |c_{\phi''}(u)\cap c_{\phi''}(v)| = 3 $, 正如情形$ 3.1.2 $, 矛盾.否则, $ c_{\phi}(v_{15}) = \{5, 7, 8, 9, $ $ 10, 12\} $.现用$ 11 $, $ s $和$ t $分别给$ v_{1}v_{11} $, $ v_{1}v_{12} $和$ vv_{1} $重新着色可得$ H $的一个$ 12 $ -邻点可区别边着色$ \phi''' $.从而$ |c_{\phi'''}(u)\cap c_{\phi'''}(v)| = 3 $, 正如情形$ 3.1.2 $, 矛盾.

假设$ |\{2, 3, 4\}\cap c_{\phi}(v_{1})| = 1 $.不妨设$ \phi(v_{1}v_{11}) = 2 $和$ \phi(v_{1}v_{1j}) = j+3 $, 其中$ j = 2, 3, 4, 5 $.若存在$ p\in C\backslash \{c_{\phi}(v)\cup c_{\phi}(v_{1})\} $, 用$ p $给$ vv_{1} $重新着色可得$ H $的一个$ 12 $ -邻点可区别边着色$ \phi' $, 从而$ |c_{\phi'}(u)\cap c_{\phi'}(v)| = 3 $, 正如情形$ 3.1.2 $, 矛盾.否则, 不妨设$ c_{\phi}(v_{11}) = \{2, 5, 6, 7, 8, 9\} $, $ c_{\phi}(v_{12}) = \{2, 5, 6, 7, 8, 10\} $, $ c_{\phi}(v_{13}) = \{2, 5, 6, 7, 8, 11\} $和$ c_{\phi}(v_{14}) = \{2, 5, 6, 7, 8, 12\} $.若存在$ q\in \{1, 3, 4\} $, 使得$ \{q, 2, 6, 7, 8, 10\}\notin \Omega_{v_{1}}(v_{12}) $, 那么先用$ q $给$ v_{1}v_{12} $重新着色.进一步, 若用$ 5 $给$ vv_{1} $重新着色可得$ H $的一个$ 12 $ -邻点可区别边着色$ \phi' $, 从而$ |c_{\phi'}(u)\cap c_{\phi'}(v)| = 3 $, 正如情形$ 3.1.2 $, 矛盾.否则, $ c_{\phi}(v_{15}) = \{q, 2, 5, 6, 7, 8\} $.现用$ 11 $给$ vv_{1} $重新着色可得$ H $的一个$ 12 $ -邻点可区别边着色$ \phi'' $.从而$ |c_{\phi''}(u)\cap c_{\phi''}(v)| = 3 $, 正如情形$ 3.1.2 $, 矛盾.否则, 在$ \phi $下, $ \{\{1, 2, 6, 7, 8, 10\}, \{2, 3, 6, 7, 8, 10\}, $ $ \{2, 4, 6, 7, 8, 10\}\}\subseteq \Omega_{v_{1}}(v_{12}) $.由于$ |\Omega_{v_{1}}(v_{12})| = 5 $, 所以存在$ r\in\{9, 11, 12\} $, 使得$ \{r, 2, 6, 7, 8, 10\}\notin \Omega_{v_{1}}(v_{12}) $, 那么先用$ r $给$ v_{1}v_{12} $重新着色.进一步, 若用$ s\in\{9, 11, 12\}\backslash\{r\} $给$ vv_{1} $重新着色可得$ H $的一个$ 12 $ -邻点可区别边着色$ \phi' $, 从而$ |c_{\phi'}(u)\cap c_{\phi'}(v)| = 3 $, 正如情形$ 3.1.2 $, 矛盾.否则, $ c_{\phi}(v_{15}) = \{r, s, 2, 6, 7, 8\} $.现用$ t\in\{9, 11, 12\}\backslash\{r, s\} $给$ vv_{1} $重新着色可得$ H $的一个$ 12 $ -邻点可区别边着色$ \phi'' $.从而$ |c_{\phi''}(u)\cap c_{\phi''}(v)| = 3 $, 正如情形$ 3.1.2 $, 矛盾.

假设$ |\{2, 3, 4\}\cap c_{\phi}(v_{1})| = 2 $.不妨设$ \phi(v_{1}v_{11}) = 2 $, $ \phi(v_{1}v_{12}) = 3 $和$ \phi(v_{1}v_{1j}) = j+2 $, 其中$ j = 3, 4, 5 $.若存在$ p\in C\backslash \{c_{\phi}(v)\cup c_{\phi}(v_{1})\} $, 用$ p $给$ vv_{1} $重新着色可得$ H $的一个$ 12 $ -邻点可区别边着色$ \phi' $, 从而$ |c_{\phi'}(u)\cap c_{\phi'}(v)| = 3 $, 正如情形$ 3.1.2 $, 矛盾.否则, 不妨设$ c_{\phi}(v_{11}) = \{2, 3, 5, 6, 7, 8\} $, $ c_{\phi}(v_{12}) = \{2, 3, 5, 6, 7, 9\} $, $ c_{\phi}(v_{13}) = \{2, 3, 5, 6, 7, 10\} $, $ c_{\phi}(v_{14}) = \{2, 3, 5, 6, 7, 11\} $和$ c_{\phi}(v_{15}) = \{2, 3, 5, 6, 7, 12\} $.若存在$ q\in \{1, 4\} $, 使得$ \{q, 2, 3, 6, 7, 10\}\notin \Omega_{v_{1}}(v_{13}) $, 那么用$ q $和$ 5 $分别给$ v_{1}v_{13} $和$ vv_{1} $重新着色可得$ H $的一个$ 12 $ -邻点可区别边着色$ \phi' $.从而$ |c_{\phi'}(u)\cap c_{\phi'}(v)| = 3 $, 正如情形$ 3.1.2 $, 矛盾.否则, 在$ \phi $下, $ \{\{1, 2, 3, 6, 7, 10\}, $ $ \{2, 3, 4, 6, 7, 10\}\}\subseteq \Omega_{v_{1}}(v_{13}) $.由于$ |\Omega_{v_{1}}(v_{13})| = 5 $, 所以存在$ r\in\{8, 9, 11, 12\} $, 使得$ \{r, 2, 3, 6, $ $ 7, 10\}\notin \Omega_{v_{1}}(v_{13}) $.现用$ r $和$ s\in \{8, 9, 11, 12\}\backslash\{r\} $分别给$ v_{1}v_{13} $和$ vv_{1} $重新着色可得$ H $的一个$ 12 $ -邻点可区别边着色$ \phi' $, 从而$ |c_{\phi'}(u)\cap c_{\phi'}(v)| = 3 $, 正如情形$ 3.1.2 $, 矛盾.

假设$ |\{2, 3, 4\}\cap c_{\phi}(v_{1})| = 3 $.由于$ |L(vv_{1})|\geq1 $, 所以存在$ p\in L(vv_{1}) $.现用$ p $给$ vv_{1} $重新着色可得$ H $的一个$ 12 $ -邻点可区别边着色$ \phi' $.从而$ |c_{\phi'}(u)\cap c_{\phi'}(v)| = 3 $, 正如情形$ 3.1.2 $, 矛盾.

在$ H $中, 假设$ d_{6}(v)\leq3 $.不妨设$ d(v_{1}) = 5 $.若$ |\{2, 3, 4\}\cap c_{\phi}(v_{1})|\geq1 $, 因而$ |L(vv_{1})|\geq1 $, 所以存在$ p\in L(vv_{1}) $.现用$ p $给$ vv_{1} $重新着色可得$ H $的一个$ 12 $ -邻点可区别边着色$ \phi' $.从而$ |c_{\phi'}(u)\cap c_{\phi'}(v)| = 3 $, 正如情形$ 3.1.2 $, 矛盾.否则, $ |\{2, 3, 4\}\cap c_{\phi}(v_{1})| = 0 $.不妨设$ \phi(v_{1}v_{1j}) = j+4 $, 其中$ j = 1, 2, 3, 4 $.若存在$ q\in C\backslash \{c_{\phi}(v)\cup c_{\phi}(v_{1})\} $, 用$ q $给$ vv_{1} $重新着色可得$ H $的一个$ 12 $ -邻点可区别边着色$ \phi' $, 从而$ |c_{\phi'}(u)\cap c_{\phi'}(v)| = 3 $, 正如情形$ 3.1.2 $, 矛盾.否则, 不妨设$ c_{\phi}(v_{11}) = \{5, 6, 7, 8, 9\} $, $ c_{\phi}(v_{12}) = \{5, 6, 7, 8, 10\} $, $ c_{\phi}(v_{13}) = \{5, 6, 7, 8, 11\} $和$ c_{\phi}(v_{14}) = \{5, 6, 7, 8, 12\} $.若存在$ r\in\{1, 2, 3, 4\} $, 使得$ \{r, 6, 7, 8, 9\}\notin \Omega_{v_{1}}(v_{11}) $, 那么用$ r $和$ 5 $分别给$ v_{1}v_{11} $和$ vv_{1} $重新着色可得$ H $的一个$ 12 $ -邻点可区别边着色$ \phi' $.从而$ |c_{\phi'}(u)\cap c_{\phi'}(v)| = 3 $, 正如情形$ 3.1.2 $, 矛盾.否则, 在$ \phi $下, $ \Omega_{v_{1}}(v_{11}) = \{\{1, 6, 7, 8, 9\}, \{2, 6, 7, 8, 9\}, \{3, 6, 7, 8, 9\}, \{4, 6, 7, 8, 9\}\} $.现用$ 10 $和$ 11 $分别给$ v_{1}v_{11} $和$ vv_{1} $重新着色可得$ H $的一个$ 12 $ -邻点可区别边着色$ \phi' $.从而$ |c_{\phi'}(u)\cap c_{\phi'}(v)| = 3 $, 正如情形$ 3.1.2 $, 矛盾.

情形3.2 假设$ d_{H}(u_{1}) = 5 $, 且$ d(u_{j}) = 6 $, 其中$ j = 2, 3, 4 $.

情形3.2.1 假设$ |c_{\phi}(u)\cap c_{\phi}(v)| = 0 $.

不妨设$ \phi(uu_{j}) = j+4 $, $ j = 1, 2, 3, 4 $.若存在$ p\in C\backslash \{c_{\phi}(v)\cup c_{\phi}(u)\} $, 用$ p $给$ uv $着色可得$ G $的一个$ 12 $ -邻点可区别边着色, 矛盾.否则, 在$ \phi $下, $ \{\{p\}\cup c_{\phi}(v)\}\in \Omega(v) $, 或$ \{\{p\}\cup c_{\phi}(u)\}\in \Omega(u) $.显然, $ C\backslash \{c_{\phi}(v)\cup c_{\phi}(u)\} = \{9, 10, 11, 12\} $.

假设$ |A_{v}\cap \{9, 10, 11, 12\}| = 3 $.因而$ |A_{u}\cap \{9, 10, 11, 12\}| = 1 $.不妨设$ c_{\phi}(v_{1}) = \{1, 2, 3, 4, 9\} $, $ c_{\phi}(v_{2}) = \{1, 2, 3, 4, 10\} $, $ c_{\phi}(v_{3}) = \{1, 2, 3, 4, 11\} $和$ c_{\phi}(u_{1}) = \{5, 6, 7, 8, 12\} $.由于$ |L(uu_{1})|\geq3 $, 所以存在$ q\in L(uu_{1}) $.若用$ q $给$ uu_{1} $重新着色, 用$ 5 $给$ uv $着色可得$ G $的一个$ 12 $ -邻点可区别边着色, 矛盾.否则, $ c_{\phi}(v_{4}) = \{1, 2, 3, 4, 5\} $.由于$ |\Omega_{v}(v_{1})| = 4 $, 所以存在$ r\in\{5, 6, 7, 8, 12\} $, 使得$ \{r, 2, 3, 4, 9\}\notin \Omega_{v}(v_{1}) $.现用$ r $给$ vv_{1} $重新着色, 用$ 10 $给$ uv $着色可得$ G $的一个$ 12 $ -邻点可区别边着色, 矛盾.

情形3.2.2 假设$ |c_{\phi}(u)\cap c_{\phi}(v)| = 1 $.不妨设$ \phi(uu_{1}) = 1 $和$ \phi(uu_{j}) = j+3 $, 其中$ j = 2, 3, 4 $.若存在$ p\in C\backslash \{c_{\phi}(v)\cup c_{\phi}(u)\} $, 用$ p $给$ uv $着色可得$ G $的一个$ 12 $ -邻点可区别边着色, 矛盾.否则, 在$ \phi $下, $ \{\{p\}\cup c_{\phi}(v)\}\in \Omega(v) $或$ \{\{p\}\cup c_{\phi}(u)\}\in \Omega(u) $.显然, $ C\backslash \{c_{\phi}(v)\cup c_{\phi}(u)\} = \{8, 9, 10, 11, 12\} $.不妨设$ c_{\phi}(v_{1}) = \{1, 2, 3, 4, 8\} $, $ c_{\phi}(v_{2}) = \{1, 2, 3, 4, 9\} $, $ c_{\phi}(v_{3}) = \{1, 2, 3, 4, 10\} $, $ c_{\phi}(v_{4}) = \{1, 2, 3, 4, 11\} $和$ c_{\phi}(u_{1}) = \{1, 5, 6, 7, 12\} $.若存在$ q\in\{5, 6, 7, 12\} $, 使得$ \{q, 1, 3, 4, 9\}\notin\Omega_{v}(v_{2}) $, 那么用$ q $给$ vv_{2} $重新着色, 用$ 2 $给$ uv $着色可得$ G $的一个$ 12 $ -邻点可区别边着色, 矛盾.否则, 在$ \phi $下, $ \Omega_{v}(v_{2}) = \{\{1, 3, 4, 5, 9\}, \{1, 3, 4, 6, 9\}, \{1, $ $ 3, 4, 7, 9\}, \{1, 3, 4, 9, 12\}\} $.现用$ 10 $给$ vv_{2} $重新着色, 用$ 11 $给$ uv $着色可得$ G $的一个$ 12 $ -邻点可区别边着色, 矛盾.

情形3.2.3 假设$ 2\leq|c_{\phi}(u)\cap c_{\phi}(v)|\leq3 $.显然, 存在$ p\in C\backslash \{c_{\phi}(v)\cup c_{\phi}(u)\} $, 用$ p $给$ uv $着色可得$ G $的一个$ 12 $ -邻点可区别边着色, 矛盾.

情形3.2.4 假设$ |c_{\phi}(u)\cap c_{\phi}(v)| = 4 $.设$ \phi(uu_{j}) = j $, 其中$ j = 1, 2, 3, 4 $.

假设$ |\{2, 3, 4\}\cap c_{\phi}(u_{1})|\geq1 $.由于$ |L(uu_{1})|\geq1 $, 所以存在$ p\in L(uu_{1}) $.现用$ p $给$ uu_{1} $重新着色可得$ H $的一个$ 12 $ -邻点可区别边着色$ \phi' $.从而$ |c_{\phi'}(u)\cap c_{\phi'}(v)| = 3 $, 正如情形$ 3.2.3 $, 矛盾.假设$ |\{2, 3, 4\}\cap c_{\phi}(u_{1})| = 0 $.设$ u_{1j}\in N_{H}(u_{1})\backslash \{u\} $, 其中$ j = 1, 2, 3, 4 $.不妨设$ \phi(u_{1}u_{1j}) = j+4 $, 其中$ j = 1, 2, 3, 4 $.若存在$ q\in C\backslash\{c_{\phi}(u)\cup c_{\phi}(u_{1})\} $, 用$ q $给$ uu_{1} $重新着色可得$ H $的一个$ 12 $ -邻点可区别边着色$ \phi' $, 从而$ |c_{\phi'}(u)\cap c_{\phi'}(v)| = 3 $, 正如情形$ 3.2.3 $, 矛盾.否则, 不妨设$ c_{\phi}(u_{11}) = \{5, 6, 7, 8, 9\} $, $ c_{\phi}(u_{12}) = \{5, 6, 7, 8, 10\} $, $ c_{\phi}(u_{13}) = \{5, 6, 7, 8, 11\} $和$ c_{\phi}(u_{14}) $ $ = \{5, 6, 7, 8, 12\} $.若存在$ r\in\{1, 2, 3, 4\} $, 使得$ \{r, 6, 7, 8, 9\}\notin \Omega_{u_{1}}(u_{11}) $, 那么用$ r $和$ 5 $分别给$ u_{1}u_{11} $和$ uu_{1} $重新着色可得$ H $的一个$ 12 $ -邻点可区别边着色$ \phi' $.从而$ |c_{\phi'}(u)\cap c_{\phi'}(v)| = 3 $, 正如情形$ 3.2.3 $, 矛盾.否则, 在$ \phi $下, $ \Omega_{u_{1}}(u_{11}) = \{\{1, 6, 7, 8, 9\}, \{2, 6, 7, 8, 9\}, \{3, $ $ 6, 7, 8, 9\}, $ $ \{4, 6, 7, 8, 9\}\} $.现用$ 10 $和$ 11 $分别给$ u_{1}u_{11} $和$ uu_{1} $重新着色可得$ H $的一个$ 12 $ -邻点可区别边着色$ \phi' $.从而$ |c_{\phi'}(u)\cap c_{\phi'}(v)| = 3 $, 正如情形$ 3.2.3 $, 矛盾.

情形3.3 假设$ d_{H}(u_{1}) = d_{H}(u_{2}) = 5 $且$ d_{H}(u_{3}) = d_{H}(u_{4}) = 6 $.

情形3.3.1 假设$ |c_{\phi}(u)\cap c_{\phi}(v)| = 0 $.不妨设$ \phi(uu_{j}) = j+4 $, $ j = 1, 2, 3, 4 $.若存在$ p\in C\backslash \{c_{\phi}(v)\cup c_{\phi}(u)\} $, 用$ p $给$ uv $着色可得$ G $的一个$ 12 $ -邻点可区别边着色, 矛盾.否则, 在$ \phi $下, $ \{\{p\}\cup c_{\phi}(v)\}\in \Omega(v) $, 或$ \{\{p\}\cup c_{\phi}(u)\}\in \Omega(u) $.显然, $ C\backslash \{c_{\phi}(v)\cup c_{\phi}(u)\} = \{9, 10, 11, 12\} $.

假设$ |A_{v}\cap \{9, 10, 11, 12\}| = 2 $.因而$ |A_{u}\cap \{9, 10, 11, 12\}| = 2 $.不妨设$ c_{\phi}(v_{1}) = \{1, 2, 3, 4, 9\} $, $ c_{\phi}(v_{2}) = \{1, 2, 3, 4, 10\} $, $ c_{\phi}(u_{1}) = \{5, 6, 7, 8, 11\} $和$ c(u_{2}) = \{5, 6, 7, 8, 12\} $.由于$ |L(uu_{1})|\geq3 $, 所以存在$ q\in L(uu_{1})\backslash c_{\phi}(u_{2}) $.现用$ q $给$ uu_{1} $重新着色, 用$ 12 $给$ uv $着色可得$ G $的一个$ 12 $ -邻点可区别边着色, 矛盾.

情形3.3.2 假设$ |c_{\phi}(u)\cap c_{\phi}(v)| = 1 $.

不妨设$ \phi(uu_{1}) = 1 $和$ \phi(uu_{j}) = j+3 $, 其中$ j = 2, 3, 4 $.若存在$ p\in C\backslash \{c_{\phi}(v)\cup c_{\phi}(u)\} $, 用$ p $给$ uv $着色可得$ G $的一个$ 12 $ -邻点可区别边着色, 矛盾.否则, 在$ \phi $下, $ \{\{p\}\cup c_{\phi}(v)\}\in \Omega(v) $, 或$ \{\{p\}\cup c_{\phi}(u)\}\in \Omega(u) $.显然, $ C\backslash \{c_{\phi}(v)\cup c_{\phi}(u)\} = \{8, 9, 10, 11, 12\} $.

假设$ |A_{v}\cap \{8, 9, 10, 11, 12\}| = 3 $.因而$ |A_{u}\cap \{8, 9, 10, 11, 12\}| = 2 $.不妨设$ c_{\phi}(v_{1}) = \{1, 2, 3, 4, 8\} $, $ c_{\phi}(v_{2}) = \{1, 2, 3, 4, 9\} $, $ c_{\phi}(v_{3}) = \{1, 2, 3, 4, 10\} $, $ c_{\phi}(u_{1}) = \{1, 5, 6, 7, 11\} $和$ c_{\phi}(u_{2}) = \{1, 5, 6, 7, 12\} $.由于$ |L(uu_{2})|\geq3 $, 所以存在$ q\in L(uu_{2})\backslash c_{\phi}(u_{1}) $.现用$ q $给$ uu_{2} $重新着色, 用$ 11 $给$ uv $着色可得$ G $的一个$ 12 $ -邻点可区别边着色, 矛盾.

情形3.3.3 假设$ |c_{\phi}(u)\cap c_{\phi}(v)| = 2 $.

不妨设$ \phi(uu_{1}) = 1 $, $ \phi(uu_{2}) = 2 $, $ \phi(uu_{3}) = 5 $和$ \phi(uu_{4}) = 6 $.若存在$ p\in C\backslash \{c_{\phi}(v)\cup c_{\phi}(u)\} $, 用$ p $给$ uv $着色可得$ G $的一个$ 12 $ -邻点可区别边着色, 矛盾.否则, 在$ \phi $下, $ \{\{p\}\cup c_{\phi}(v)\}\in \Omega(v) $或$ \{\{p\}\cup c_{\phi}(u)\}\in \Omega(u) $.显然, $ C\backslash \{c_{\phi}(v)\cup c_{\phi}(u)\} = \{7, 8, 9, 10, 11, 12\} $.不妨设$ c_{\phi}(v_{1}) = \{1, 2, 3, 4, 7\} $, $ c_{\phi}(v_{2}) = \{1, 2, 3, 4, 8\} $, $ c_{\phi}(v_{3}) = \{1, 2, 3, 4, 9\} $, $ c_{\phi}(v_{4}) = \{1, 2, 3, 4, 10\} $, $ c_{\phi}(u_{1}) = \{1, 2, 5, 6, 11\} $和$ c_{\phi}(u_{2}) = \{1, 2, 5, 6, 12\} $.由于$ |L(uu_{1})|\geq3 $, 所以存在$ q\in L(uu_{1})\backslash c_{\phi}(u_{2}) $.现用$ q $给$ uu_{1} $重新着色, 用$ 12 $给$ uv $着色可得$ G $的一个$ 12 $ -邻点可区别边着色, 矛盾.

情形3.3.4 假设$ |c_{\phi}(u)\cap c_{\phi}(v)| = 3 $.显然, 存在$ p\in C\backslash \{c_{\phi}(v)\cup c_{\phi}(u)\} $, 用$ p $给$ uv $着色可得$ G $的一个$ 12 $ -邻点可区别边着色, 矛盾.

情形3.3.5 假设$ |c_{\phi}(u)\cap c_{\phi}(v)| = 4 $.与情形$ 3.2.4 $类似, 矛盾.

情形3.4 假设$ d(u_{j}) = 5 $, 其中$ j = 1, 2, 3 $, 且$ d(u_{4}) = 6 $.

情形3.4.1 假设$ |c_{\phi}(u)\cap c_{\phi}(v)| = 0 $.

不妨设$ \phi(uu_{j}) = j+4 $, $ j = 1, 2, 3, 4 $.若存在$ p\in C\backslash \{c_{\phi}(v)\cup c_{\phi}(u)\} $, 用$ p $给$ uv $着色可得$ G $的一个$ 12 $ -邻点可区别边着色, 矛盾.否则, 在$ \phi $下, $ \{\{p\}\cup c_{\phi}(v)\}\in \Omega(v) $或$ \{\{p\}\cup c_{\phi}(u)\}\in \Omega(u) $.显然, $ C\backslash \{c_{\phi}(v)\cup c_{\phi}(u)\} = \{9, 10, 11, 12\} $.

假设$ |A_{v}\cap \{9, 10, 11, 12\}| = 4 $.不妨设$ c_{\phi}(v_{1}) = \{1, 2, 3, 4, 9\} $, $ c_{\phi}(v_{2}) = \{1, 2, 3, 4, 10\} $, $ c_{\phi}(v_{3}) = \{1, 2, 3, 4, 11\} $和$ c_{\phi}(v_{4}) = \{1, 2, 3, 4, 12\} $.若存在$ q\in\{5, 6, 7, 8\} $, 使得$ \{q, 2, 3, 4, 9\}\notin \Omega_{v}(v_{1}) $, 那么先用$ q $给$ vv_{1} $重新着色.进一步, 若用$ 1 $给$ uv $着色可得$ G $的一个$ 12 $ -邻点可区别边着色, 矛盾.否则, $ c_{\phi}(u_{1}) = \{1, 5, 6, 7, 8\} $或$ c_{\phi}(u_{2}) = \{1, 5, 6, 7, 8\} $或$ c_{\phi}(u_{3}) = \{1, 5, 6, 7, 8\} $.不妨设$ c_{\phi}(u_{1}) = \{1, 5, 6, 7, 8\} $.若用$ 10 $给$ uv $着色可得$ G $的一个$ 12 $ -邻点可区别边着色, 矛盾.否则, $ c_{\phi}(u_{2}) = \{5, $ $ 6, 7, 8, 10\} $或$ c_{\phi}(u_{3}) = \{5, 6, 7, 8, 10\} $.不妨设$ c_{\phi}(u_{2}) = \{5, 6, 7, 8, 10\} $.若用$ 11 $给$ uv $着色可得$ G $的一个$ 12 $ -邻点可区别边着色, 矛盾.否则, $ c_{\phi}(u_{3}) = \{5, 6, 7, 8, 11\} $.现用$ 12 $给$ uv $着色可得$ G $的一个$ 12 $ -邻点可区别边着色, 矛盾.否则, 在$ \phi $下, $ \Omega_{v}(v_{1}) = \{\{2, 3, 4, 5, 9\}, $ $ \{2, 3, 4, 6, 9\}, \{2, 3, 4, 7, 9\}, \{2, 3, 4, 8, 9\}\} $.类似的, $ \Omega_{v}(v_{2}) = \{\{1, 3, 4, 5, 10\}, \{1, 3, 4, 6, 10\}, \{1, 3, $ $ 4, 7, 10\}, \{1, 3, 4, 8, 10\}\} $, $ \Omega_{v}(v_{3}) = \{\{1, 2, 4, 5, 11\}, \{1, 2, 4, 6, 11\}, \{1, 2, 4, 7, 11\}, \{1, 2, 4, 8, 11\}\} $和$ \Omega_{v}(v_{4}) = \{\{1, 2, 3, 5, 12\}, \{1, 2, $ $ 3, 6, 12\}, \{1, 2, 3, 7, 12\}, \{1, 2, 3, 8, 12\}\} $.先用$ 10 $, $ 11 $, $ 12 $和$ 9 $分别给$ vv_{1} $, $ vv_{2} $, $ vv_{3} $和$ vv_{4} $重新着色.进一步, 若用$ 1 $给$ uv $着色可得$ G $的一个$ 12 $ -邻点可区别边着色, 矛盾.否则, $ c_{\phi}(u_{1}) = \{1, 5, 6, 7, 8\} $或$ c_{\phi}(u_{2}) = \{1, 5, 6, 7, 8\} $或$ c_{\phi}(u_{3}) = \{1, 5, 6, 7, 8\} $.不妨设$ c_{\phi}(u_{1}) = \{1, 5, 6, 7, 8\} $.若用$ 2 $给$ uv $着色可得$ G $的一个$ 12 $ -邻点可区别边着色, 矛盾.否则, $ c_{\phi}(u_{2}) = \{2, 5, 6, 7, 8\} $或$ c_{\phi}(u_{3}) $ $ = \{2, 5, 6, 7, 8\} $.不妨设$ c_{\phi}(u_{2}) = \{2, 5, 6, 7, 8\} $.若用$ 3 $给$ uv $着色可得$ G $的一个$ 12 $ -邻点可区别边着色, 矛盾.否则, $ c_{\phi}(u_{3}) = \{3, 5, 6, 7, 8\} $.现用$ 4 $给$ uv $着色可得$ G $的一个$ 12 $ -邻点可区别边着色, 矛盾.

假设$ |A_{v}\cap \{9, 10, 11, 12\}| = 3 $.因而$ |A_{u}\cap \{9, 10, 11, 12\}|\geq1 $.不妨设$ c_{\phi}(v_{1}) = \{1, 2, 3, 4, 9\} $, $ c_{\phi}(v_{2}) = \{1, 2, 3, 4, 10\} $, $ c_{\phi}(v_{3}) = \{1, 2, 3, 4, 11\} $和$ c_{\phi}(u_{1}) = \{5, 6, 7, 8, 12\} $.由于$ |L(uu_{1})|\geq3 $, 所以存在$ q\in L(uu_{1}) $.若用$ q $给$ uu_{1} $重新着色, 用$ 5 $给$ uv $着色可得$ G $的一个$ 12 $ -邻点可区别边着色, 矛盾.否则, $ c_{\phi}(u_{2}) = \{q, 5, 6, 7, 8\} $或$ c_{\phi}(u_{3}) = \{q, 5, 6, 7, 8\} $或$ c_{\phi}(v_{4}) = \{1, 2, 3, 4, 5\} $.若$ c_{\phi}(v_{4}) = \{1, 2, 3, 4, 5\} $, 显然, 存在$ r\in\{5, 6, 7, 8, 12\} $, 使得$ \{r, 2, 3, 4, 9\}\notin \Omega_{v}(v_{1}) $, 那么先用$ r $给$ vv_{1} $重新着色.进一步, 若用$ 10 $给$ uv $着色可得$ G $的一个$ 12 $ -邻点可区别边着色, 矛盾.否则, $ c_{\phi}(u_{2}) = \{5, 6, 7, 8, 10\} $或$ c_{\phi}(u_{3}) = \{5, 6, 7, 8, 10\} $.不妨设$ c_{\phi}(u_{2}) = \{5, 6, 7, 8, 10\} $.若用$ 11 $给$ uv $着色可得$ G $的一个$ 12 $ -邻点可区别边着色, 矛盾.否则, $ c_{\phi}(u_{3}) = \{5, 6, 7, 8, 11\} $.显然存在$ s\in\{6, 7\}\backslash\{r\} $, 不妨设$ s = 7 $.由于$ |L(uu_{3})|\geq3 $, 所以存在$ t\in L(uu_{3})\backslash\{c_{\phi}(u_{1})\cup c_{\phi}(u_{2})\} $.现用$ t $给$ uu_{3} $重新着色, 用$ 7 $给$ uv $着色可得$ G $的一个$ 12 $ -邻点可区别边着色, 矛盾.若$ c_{\phi}(u_{2}) = \{q, $ $ 5, 6, 7, 8\} $或$ c_{\phi}(u_{3}) = \{q, 5, 6, 7, 8\} $, 不妨设$ c_{\phi}(u_{2}) = \{q, 5, 6, 7, 8\} $.由于$ |L(uu_{2})|\geq3 $, 所以存在$ r\in L(uu_{2}) $ $ \backslash c_{\phi}(u_{1}) $.若用$ r $给$ uu_{2} $重新着色, 用$ 12 $给$ uv $着色可得$ G $的一个$ 12 $ -邻点可区别边着色, 矛盾.否则, $ c_{\phi}(u_{3}) = \{r, 5, 7, 8, 12\} $.由于$ |L(uu_{3})|\geq2 $, 所以存在$ s\in L(uu_{3}) $.显然, $ s\notin c_{\phi}(u_{1}) $, $ 6\notin c_{\phi}(u_{3}) $和$ 12\notin c_{\phi}(u_{2}) $.因而用$ s $给$ uu_{3} $重新着色, 用$ 12 $给$ uv $着色可得$ G $的一个$ 12 $ -邻点可区别边着色, 矛盾.

假设$ |A_{v}\cap \{9, 10, 11, 12\}| = 2 $.因而$ |A_{u}\cap \{9, 10, 11, 12\}|\geq2 $.不妨设$ c_{\phi}(v_{1}) = \{1, 2, $ $ 3, 4, 9\} $, $ c_{\phi}(v_{2}) = \{1, 2, 3, 4, 10\} $, $ c_{\phi}(u_{1}) = \{5, 6, 7, 8, 11\} $和$ c_{\phi}(u_{2}) = \{5, 6, 7, 8, 12\} $.由于$ |L(uu_{1})|\geq3 $, 所以存在$ q\in L(uu_{1})\backslash c_{\phi}(u_{2}) $.若用$ q $给$ uu_{1} $重新着色, 用$ 12 $给$ uv $着色可得$ G $的一个$ 12 $ -邻点可区别边着色, 矛盾.否则, $ c_{\phi}(u_{3}) = \{q, 6, 7, 8, 12\} $.由于$ |L(uu_{2})|\geq3 $, 所以存在$ r\in L(uu_{2})\backslash \{c_{\phi}(u_{1})\cup c_{\phi}(u_{3})\} $.现用$ r $给$ uu_{2} $重新着色, 用$ 11 $给$ uv $着色可得$ G $的一个$ 12 $ -邻点可区别边着色, 矛盾.

假设$ |A_{v}\cap \{9, 10, 11, 12\}| = 1 $.因而$ |A_{u}\cap \{9, 10, 11, 12\}| = 3 $.不妨设$ c_{\phi}(v_{1}) = \{1, 2, $ $ 3, 4, 9\} $, $ c_{\phi}(u_{1}) = \{5, 6, 7, 8, 10\} $, $ c_{\phi}(u_{2}) = \{5, 6, 7, 8, 11\} $和$ c_{\phi}(u_{3}) = \{5, 6, 7, 8, 12\} $.由于$ |L(uu_{1})|\geq3 $, 所以存在$ q\in L(uu_{1})\backslash\{c_{\phi}(u_{2})\cup c_{\phi}(u_{3})\} $.现用$ q $给$ uu_{1} $重新着色, 用$ 11 $给$ uv $着色可得$ G $的一个$ 12 $ -邻点可区别边着色, 矛盾.

情形3.4.2 假设$ |c_{\phi}(u)\cap c_{\phi}(v)| = 1 $.

不妨设$ \phi(uu_{1}) = 1 $, $ \phi(uu_{j}) = j+3 $, $ j = 2, 3, 4 $.若存在$ p\in C\backslash \{c_{\phi}(v)\cup c_{\phi}(u)\} $, 用$ p $给$ uv $着色可得$ G $的一个$ 12 $ -邻点可区别边着色, 矛盾.否则, 在$ \phi $下, $ \{\{p\}\cup c_{\phi}(v)\}\in \Omega(v) $或$ \{\{p\}\cup c_{\phi}(u)\}\in \Omega(u) $.显然, $ C\backslash \{c_{\phi}(v)\cup c_{\phi}(u)\} = \{8, 9, 10, 11, 12\} $.

假设$ |A_{v}\cap \{8, 9, 10, 11, 12\}| = 4 $.因而$ |A_{u}\cap \{8, 9, 10, 11, 12\}|\geq1 $.不妨设$ c_{\phi}(v_{1}) = \{1, 2, 3, 4, 8\} $, $ c_{\phi}(v_{2}) = \{1, 2, 3, 4, 9\} $, $ c_{\phi}(v_{3}) = \{1, 2, 3, 4, 10\} $, $ c_{\phi}(v_{4}) = \{1, 2, 3, 4, 11\} $和$ c_{\phi}(u_{1}) = \{1, 5, 6, 7, 12\} $.若存在$ q\in\{5, 6, 7, 12\} $, 使得$ \{q, 1, 3, 4, 9\}\notin \Omega_{v}(v_{2}) $, 那么先用$ q $给$ vv_{2} $重新着色.进一步, 若用$ 2 $给$ uv $着色可得$ G $的一个$ 12 $ -邻点可区别边着色, 矛盾.否则, $ c_{\phi}(u_{2}) = \{1, 2, 5, 6, 7\} $或$ c_{\phi}(u_{3}) = \{1, 2, 5, 6, 7\} $.不妨设$ c_{\phi}(u_{2}) = \{1, 2, 5, 6, 7\} $.若用$ 8 $给$ uv $着色可得$ G $的一个$ 12 $ -邻点可区别边着色, 矛盾.否则, $ c_{\phi}(u_{3}) = \{1, 5, 6, 7, 8\} $.现用$ 10 $给$ uv $着色可得$ G $的一个$ 12 $ -邻点可区别边着色, 矛盾.否则, 在$ \phi $下, $ \Omega_{v}(v_{2}) = \{\{1, 3, 4, 5, 9\}, \{1, 3, 4, 6, 9\}, \{1, $ $ 3, 4, 7, 9\}, \{1, 3, 4, 9, 12\}\} $.类似的, $ \Omega_{v}(v_{3}) = \{\{1, 2, 4, 5, 10\}, \{1, 2, 4, 6, 10\}, \{1, 2, 4, 7, 10\}, $ $ \{1, 2, 4, 10, 12\}\} $和$ \Omega_{v}(v_{4}) = \{\{1, 2, 3, 5, $ $ 11\}, \{1, 2, 3, 6, 11\}, \{1, 2, 3, 7, 11\}, $ $ \{1, 2, 3, 11, 12\}\} $.先用$ 10 $, $ 11 $和$ 9 $分别给$ vv_{2} $, $ vv_{3} $和$ vv_{4} $重新着色.进一步, 若用$ 2 $给$ uv $着色可得$ G $的一个$ 12 $ -邻点可区别边着色, 矛盾.否则, $ c_{\phi}(u_{2}) = \{1, 2, $ $ 5, 6, 7\} $或$ c_{\phi}(u_{3}) = \{1, 2, 5, 6, 7\} $.不妨设$ c_{\phi}(u_{2}) = \{1, 2, 5, 6, 7\} $.若用$ 3 $给$ uv $着色可得$ G $的一个$ 12 $ -邻点可区别边着色, 矛盾.否则, $ c_{\phi}(u_{3}) = \{1, 3, 5, 6, 7\} $.现用$ 4 $给$ uv $着色可得$ G $的一个$ 12 $ -邻点可区别边着色, 矛盾.

假设$ |A_{v}\cap \{8, 9, 10, 11, 12\}| = 3 $.因而$ |A_{u}\cap \{8, 9, 10, 11, 12\}|\geq2 $.不妨设$ c_{\phi}(v_{1}) = \{1, 2, 3, 4, 8\} $, $ c_{\phi}(v_{2}) = \{1, 2, $ $ 3, 4, 9\} $, $ c_{\phi}(v_{3}) = \{1, 2, 3, 4, 10\} $, $ c_{\phi}(u_{1}) = \{1, 5, 6, 7, 11\} $和$ c_{\phi}(u_{2}) = \{1, 5, 6, 7, 12\} $.由于$ |L(uu_{1})|\geq3 $, 所以存在$ q\in L(uu_{1})\backslash c_{\phi}(u_{2}) $.若用$ q $给$ uu_{1} $重新着色, 用$ 12 $给$ uv $着色可得$ G $的一个$ 12 $ -邻点可区别边着色, 矛盾.否则, $ c_{\phi}(u_{3}) = \{q, 5, 6, 7, 12\} $.由于$ |L(uu_{2})|\geq3 $, 所以存在$ r\in L(uu_{2})\backslash\{ c_{\phi}(u_{1})\cup c_{\phi}(u_{3})\} $.现用$ r $给$ uu_{2} $重新着色, 用$ 11 $给$ uv $着色可得$ G $的一个$ 12 $ -邻点可区别边着色, 矛盾.

假设$ |A_{v}\cap \{8, 9, 10, 11, 12\}| = 2 $.因而$ |A_{u}\cap \{8, 9, 10, 11, 12\}| = 3 $.不妨设$ c_{\phi}(v_{1}) = \{1, 2, 3, 4, 8\} $, $ c_{\phi}(v_{2}) = \{1, 2, 3, 4, 9\} $, $ c_{\phi}(u_{1}) = \{1, 5, 6, 7, 10\} $, $ c_{\phi}(u_{2}) = \{1, 5, 6, 7, 11\} $和$ c_{\phi}(u_{3}) = \{1, 5, 6, 7, 12\} $.由于$ |L(uu_{2})|\geq3 $, 所以存在$ q\in L(uu_{2})\backslash\{c_{\phi}(u_{1})\cup c_{\phi}(u_{3})\} $.现用$ q $给$ uu_{2} $重新着色, 用$ 12 $给$ uv $着色可得$ G $的一个$ 12 $ -邻点可区别边着色, 矛盾.

情形3.4.3 假设$ |c_{\phi}(u)\cap c_{\phi}(v)| = 2 $.

假设$ |A_{v}\cap \{7, 8, 9, 10, 11, 12\}| = 4 $.因而$ |A_{u}\cap \{7, 8, 9, 10, 11, 12\}|\geq2 $.不妨设$ c_{\phi}(v_{1}) = \{1, 2, 3, 4, 7\} $, $ c_{\phi}(v_{2}) = \{1, 2, 3, 4, 8\} $, $ c_{\phi}(v_{3}) = \{1, 2, 3, 4, 9\} $, $ c_{\phi}(v_{4}) = \{1, 2, 3, 4, 10\} $, $ c_{\phi}(u_{1}) = \{1, 2, 5, 6, 11\} $和$ c_{\phi}(u_{2}) = \{1, 2, 5, 6, 12\} $.由于$ |L(uu_{1})|\geq3 $, 所以存在$ q\in L(uu_{1})\backslash c_{\phi}(u_{2}) $.若用$ q $给$ uu_{1} $重新着色, 用$ 12 $给$ uv $着色可得$ G $的一个$ 12 $ -邻点可区别边着色, 矛盾.否则, $ c_{\phi}(u_{3}) = \{q, 2, 5, 6, 12\} $.由于$ |L(uu_{2})|\geq3 $, 所以存在$ r\in L(uu_{2})\backslash\{c_{\phi}(u_{1})\cup c_{\phi}(u_{3})\} $.现用$ r $给$ uu_{2} $重新着色, 用$ 11 $给$ uv $着色可得$ G $的一个$ 12 $ -邻点可区别边着色, 矛盾.

假设$ |A_{v}\cap \{7, 8, 9, 10, 11, 12\}| = 3 $.因而$ |A_{u}\cap \{7, 8, 9, 10, 11, 12\}| = 3 $.不妨设$ c_{\phi}(v_{1}) = \{1, 2, 3, 4, 7\} $, $ c_{\phi}(v_{2}) = \{1, 2, 3, 4, 8\} $, $ c_{\phi}(v_{3}) = \{1, 2, 3, 4, 9\} $, $ c_{\phi}(u_{1}) = \{1, 2, 5, 6, 10\} $, $ c_{\phi}(u_{2}) = \{1, 2, 5, 6, 11\} $和$ c_{\phi}(u_{3}) = \{1, 2, 5, 6, 12\} $.由于$ |L(uu_{3})|\geq3 $, 所以存在$ q\in L(uu_{3})\backslash\{c_{\phi}(u_{1})\cup c_{\phi}(u_{2})\} $.现用$ q $给$ uu_{3} $重新着色, 用$ 10 $给$ uv $着色可得$ G $的一个$ 12 $ -邻点可区别边着色, 矛盾.

情形3.4.4 假设$ |c_{\phi}(u)\cap c_{\phi}(v)| = 3 $.

不妨设$ \phi(uu_{j}) = j $, 其中$ j = 1, 2, 3 $.设$ \phi(uu_{4}) = 5 $.若存在$ p\in C\backslash \{c_{\phi}(v)\cup c_{\phi}(u)\} $, 用$ p $给$ uv $着色可得$ G $的一个$ 12 $ -邻点可区别边着色, 矛盾.否则, 在$ \phi $下, $ \{\{p\}\cup c_{\phi}(v)\}\in \Omega(v) $或$ \{\{p\}\cup c_{\phi}(u)\}\in \Omega(u) $.显然, $ C\backslash \{c_{\phi}(v)\cup c_{\phi}(u)\} = \{6, 7, 8, 9, 10, 11, 12\} $.不妨设$ c_{\phi}(v_{1}) = \{1, 2, 3, 4, 6\} $, $ c_{\phi}(v_{2}) = \{1, 2, 3, 4, 7\} $, $ c_{\phi}(v_{3}) = \{1, 2, 3, 4, 8\} $, $ c_{\phi}(v_{4}) = \{1, 2, 3, 4, 9\} $, $ c_{\phi}(u_{1}) = \{1, 2, 3, 5, 10\} $, $ c_{\phi}(u_{2}) = \{1, 2, 3, 5, 11\} $和$ c_{\phi}(u_{3}) = \{1, 2, 3, 5, 12\} $.由于$ |L(uu_{1})|\geq3 $, 所以存在$ q\in L(uu_{1})\backslash\{ c_{\phi}(u_{2})\cup c_{\phi}(u_{3})\} $.现用$ q $给$ uu_{1} $重新着色, 用$ 11 $给$ uv $着色可得$ G $的一个$ 12 $邻点可区别边着色, 矛盾.

情形3.4.5 假设$ |c_{\phi}(u)\cap c_{\phi}(v)| = 4 $.与情形$ 3.2.4 $类似, 矛盾.

情形3.5 假设$ d(u_{j}) = 5 $, 其中$ j = 1, 2, 3, 4 $.由于$ G $是最大度为6的连通图, 所以在$ G $中存在一个$ 6 $ -顶点$ w $, 和一条最短路$ p = w_{0}, w_{1}, $ $ \cdots, w_{t} $, 其中$ w_{0} = u $, $ w_{t} = w $.设$ w_{s} $是这条路上的第一个$ 6 $ -顶点.根据情形$ 1 $, $ 2 $和3.1–3.4可知$ d(w_{k}) = 5 $且$ s\geq3 $, 其中$ k = 0, 1, \cdots, s-1 $.因此找到了一个$ 5 $ -顶点$ w_{s-1} $和一个$ 6 $ -顶点$ w_{s} $相邻.令$ H = G-w_{s-2}w_{s-1} $.正如前面已讨论, 矛盾.因此这个定理成立.

推论2.1 设$ G $是一个最大度为6的图, 则$ \chi'_{a}(G)\leq13 $.

证由引理$ 1.1 $和定理$ 2.1 $可得.

参考文献

[1]	Zhang Zhongfu, Liu Linzhong, Wang Jianfang. Adjacent strong edge coloring of graphs[J]. Appl. Math. Lett., 2002, 15(5): 623–626. DOI:10.1016/S0893-9659(02)80015-5

[2]	Hatami H. △ +300 is a bound on the adjacent vertex distinguishing edge chromatic number[J]. J. Combin. Theory Ser. B., 2006, 95(2): 246–256.

[3]	Akbari S, Bidkhori H, Nosrati N. r-Strong edge colorings of graphs[J]. Disc. Math., 2006, 306(23): 3005–3010. DOI:10.1016/j.disc.2004.12.027

[4]	Zhang Lianzhu, Wang Weifan, Lih K W. An improved upper bound on the adjacent vertex distinguishing chromatic index of a graph[J]. Disc. Appl. Math., 2014, 162(C): 348–354.

[5]	Balister P N, Györi J, Lehel R H, Schelp R H. Adjacent vertex distinguish edge-coloring[J]. SIAM J. Disc. Math., 2007, 21(1): 237–250.

[6]	Hocquard H, Montassier M. Adjacent vertex-distinguishing edge coloring of graphs with maximum degree △[J]. J. Comb. Optim., 2013, 26(1): 152–160. DOI:10.1007/s10878-011-9444-9

[7]	Wang Yiqiao, Wang Weifan, Huo Jingjing. Some bounds on the neighbor-distinguishing index of graphs[J]. Disc. Math., 2015, 338(11): 2006–2013. DOI:10.1016/j.disc.2015.05.007