点可区别边色数和点可区别全色数的两个上界
- 格式：pdf
- 大小：208.01 KB
- 文档页数：4
文档推荐
-
近完全图的邻点可区别正常边色数页数:7
-
点可区别边色数和点可区别全色数的两个上界页数:4
-
Wm∨C4的点可区别正常边色数页数:3
下载文档原格式
合集下载
图的D(2)-点可区别一般边染色
高校应用数学学报
２ ０ １ ３ ， ２ ８ （ ２ ） ： ２ １ １ — ２ ２ １
图的Ｄ（ ２ ） 一 点可区别一般边染色
陈祥 恩木 ， 赵飞虎， 胡志涛， 李泽鹏， 姚
（ 西北师范大学 数 学与统计 学院， 甘肃兰州 ７ ３ ０ ０ ７ ０ ）
兵
摘
要 ： 引入 了 图的Ｄ（ ） 一 点 可 区别 一般 边 染 色， 并对 ＝ ２ 的情形 做 了讨论， 得 到
引理 １ ． １ 【 】 对阶 数 至 少 为３ 的 路Ｐ， 有） （ ２ （ Ｐ）＝ ３ ；且 对 阶数 等 于３ 的 圈ｃ（ ｋ 为正 整 数） ， 有） ／ ２ （ Ｃ）＝ ３ ；对 阶 数ｎ 不 被３ 整 除 且 不等 于５ 的 圈 ，有ｘ ２ （ Ｃ ￣ ）＝ ４ ；对 阶 数 等 于５ 的 圈 ，
§ １ 引言及 准备 工作
图的染 色 问题具有重 要的理论意义及 实际意义， 研究 图的染 色 问题 就是确定各类 图的各种 染色色数 的具体值或上下 界． 本文主 要讨论 了图的Ｄ（ ２ ） 一 点可区别一般边染色， 仅考虑简单无 向
有 限 图ห้องสมุดไป่ตู้
所谓 图Ｇ的一个ｋ 一 一般边 染色（ 或使用 了 种颜 色的一般 边染色） － 厂 是指 种颜 色１ ， ２ ， … ， 关 于Ｇ的全体边 的一个分配（ 注意分配给相邻边的颜色可 以相 同） ． Ｖ ∈ （ Ｇ） ， 用Ｓ ｆ （ Ｘ ） （ 或不致 引起
混淆 时， 记为Ｓ （ ） ） 表示在 ， 下与Ｘ 关 联的边 的颜色 作成的集合（ 非多重集） ， 称之 为在， 下点Ｘ 的色
集合． 对 ， Ｙ∈ （ Ｇ） ， 若ｓ （ ｘ ） ≠ｓ （ ） ， 则称 与Ｙ 可 区别 ． 以下用ｄ （ ｕ ， ） 表示图Ｇ中任意两 点 ， 之
２ ０ １ ３ ， ２ ８ （ ２ ） ： ２ １ １ — ２ ２ １
图的Ｄ（ ２ ） 一 点可区别一般边染色
陈祥 恩木 ， 赵飞虎， 胡志涛， 李泽鹏， 姚
（ 西北师范大学 数 学与统计 学院， 甘肃兰州 ７ ３ ０ ０ ７ ０ ）
兵
摘
要 ： 引入 了 图的Ｄ（ ） 一 点 可 区别 一般 边 染 色， 并对 ＝ ２ 的情形 做 了讨论， 得 到
引理 １ ． １ 【 】 对阶 数 至 少 为３ 的 路Ｐ， 有） （ ２ （ Ｐ）＝ ３ ；且 对 阶数 等 于３ 的 圈ｃ（ ｋ 为正 整 数） ， 有） ／ ２ （ Ｃ）＝ ３ ；对 阶 数ｎ 不 被３ 整 除 且 不等 于５ 的 圈 ，有ｘ ２ （ Ｃ ￣ ）＝ ４ ；对 阶 数 等 于５ 的 圈 ，
§ １ 引言及 准备 工作
图的染 色 问题具有重 要的理论意义及 实际意义， 研究 图的染 色 问题 就是确定各类 图的各种 染色色数 的具体值或上下 界． 本文主 要讨论 了图的Ｄ（ ２ ） 一 点可区别一般边染色， 仅考虑简单无 向
有 限 图ห้องสมุดไป่ตู้
所谓 图Ｇ的一个ｋ 一 一般边 染色（ 或使用 了 种颜 色的一般 边染色） － 厂 是指 种颜 色１ ， ２ ， … ， 关 于Ｇ的全体边 的一个分配（ 注意分配给相邻边的颜色可 以相 同） ． Ｖ ∈ （ Ｇ） ， 用Ｓ ｆ （ Ｘ ） （ 或不致 引起
混淆 时， 记为Ｓ （ ） ） 表示在 ， 下与Ｘ 关 联的边 的颜色 作成的集合（ 非多重集） ， 称之 为在， 下点Ｘ 的色
集合． 对 ， Ｙ∈ （ Ｇ） ， 若ｓ （ ｘ ） ≠ｓ （ ） ， 则称 与Ｙ 可 区别 ． 以下用ｄ （ ｕ ， ） 表示图Ｇ中任意两 点 ， 之
点可区别边染色的研究
5 8d + 4 d 8d
数 x 同时使得不等式
1 8 ≤( ) x 2
1−
( min ≤ d ≤ max )
8d 2 8d
1 8 ( )d ≤ ( ) x 2
成立，则有
d −1+
( min ≤ d ≤ max )
X 1' S (G ) ≤ x∆
证明： 令 ∆ = d ， f : E → { 1， 2， L , xd 是从颜色 { 1，2，L , xd 下两个条件： （ A ）正常边染色——没有两条相邻的边染成同一种颜色。 （ B ）点可区别——没有任何两个顶点关联同样的颜色集合。 为了应用一般局部引理，我们定义如下两个坏事件： （ I ）对任意一对相邻的边 A = {ε 1 , ε 2 } ，令 E A 表示 ε 1 和 ε 2 被染成同种颜色的事件。 （ II ）对任意两点 u , v ∈ V (G ) ，如果 C (u ) = C (v) ，令 E B 表示 C (u ) = C (v) 的事件。 注意到如果（ I ）和（ II ）都不发生，则 f 是 G 的点可区别的边染色。 为了运用一般局部引理，我们需进行以下几步： （1）计算坏事件发生的概率
m(6) = 0.5776030349614399 m(7) = 0.5658708498213858
m(8) = 0.5571918979989056
m(9) = 0.550528193021916
m(10) = 0.5452538381738173
所以（9）式显然成立 对（10）式我们有
n( x) -------------------------- q( x)
1 ⎞ ⎛ ⎟ ⎜1 − ⎝ 8d ⎠
1 ⎞ ⎛ ⎜1 − d ⎟ ⎝ 8 ⎠ 8 ⎛1⎞ ≤⎜ ⎟ x ⎝4⎠
数 x 同时使得不等式
1 8 ≤( ) x 2
1−
( min ≤ d ≤ max )
8d 2 8d
1 8 ( )d ≤ ( ) x 2
成立，则有
d −1+
( min ≤ d ≤ max )
X 1' S (G ) ≤ x∆
证明： 令 ∆ = d ， f : E → { 1， 2， L , xd 是从颜色 { 1，2，L , xd 下两个条件： （ A ）正常边染色——没有两条相邻的边染成同一种颜色。 （ B ）点可区别——没有任何两个顶点关联同样的颜色集合。 为了应用一般局部引理，我们定义如下两个坏事件： （ I ）对任意一对相邻的边 A = {ε 1 , ε 2 } ，令 E A 表示 ε 1 和 ε 2 被染成同种颜色的事件。 （ II ）对任意两点 u , v ∈ V (G ) ，如果 C (u ) = C (v) ，令 E B 表示 C (u ) = C (v) 的事件。 注意到如果（ I ）和（ II ）都不发生，则 f 是 G 的点可区别的边染色。 为了运用一般局部引理，我们需进行以下几步： （1）计算坏事件发生的概率
m(6) = 0.5776030349614399 m(7) = 0.5658708498213858
m(8) = 0.5571918979989056
m(9) = 0.550528193021916
m(10) = 0.5452538381738173
所以（9）式显然成立 对（10）式我们有
n( x) -------------------------- q( x)
1 ⎞ ⎛ ⎟ ⎜1 − ⎝ 8d ⎠
1 ⎞ ⎛ ⎜1 − d ⎟ ⎝ 8 ⎠ 8 ⎛1⎞ ≤⎜ ⎟ x ⎝4⎠
直积图的邻点可区别全染色
ｆ ｕ ） ｆ（ｖ ≠ （ ） （ｖ ， ｕ ） ；
Ｅ ）直 积图 ×Ｇ ， ２的顶 点集 为 ， × ， （ ， ） 点 “， ，
与 （ ２ｖ ） “ ，ｚ 相邻 当且 仅 当 Ｕ Ｕ ∈Ｅ１ 一 ∈ 或 １２ ，
者 Ｕ ＝“ ∈Ｖｌ Ｖ ∈Ｅ２ ｌ ２ ， ２ ．
（ Ｃｏｌ ｇ ｆＭ ａ ｈ ｍａ ｉｓａ ｄ Ｉ ｆｒ ｔｏ ｃｅ ｃ ，Ｎｏ ｔ ｗｅ ｔＮｏ ｍａ ｉｅ ｓｔ ｌ ｅｏ ｔ ｅ ｔ ｎ ｎｏ ｍａ ｉｎ Ｓ ｉｎ ｅ ｅ ｃ ｒｈ ｓ ｒ ｌＵｎｖ ｒ ｉ ｙ，Ｌａ ｈ ｕ ￣ ｏ ７ ０ ０，Ｃｈｉａ ３ ０７ ｎ）
ｃ ｌｒｎ ｕ ｅ ｎ Ｃ ｒｅ ｉｎ ｐ ｏ ｕ ｔＧＸ ｏｏ ｉ ｇ ｎ ｍｂ ｒｏ ａ ｔｓａ ｒ ｄ ｃ Ｐ ａ ｄ Ｇ× Ｃ ｗｈ ｒ ｗａ ｔ ｒ ｆｎ ｏ ｅ １ ｎ ｍ， ｅ ｅＧ ｓａｓａ ，ａ ｒｗｈ ｅ．
Ｋｅ ｒ ｓ ａ ｒｅ ｉ ｒ ｄ ｃ ｏ ｒｐ ｓ ｄａｅ ｔｖｒｅ ｉ ｉ ｕｓ ｉｇ ｔｔｌ ｏｏ ｉｇ ｄａｅ ｔｖ ｒｅ ｙ ｗｏ ｄ ：Ｃ ｔｓ ｎ ｐｏ ｕ ｔ ｆ ａ ｈ ；ａｊｃｎ ｅｔｘ ｄｓ ｎ ｉ ｎ ｏａ ｌ ｎ ；ａｊｃｎ ｅｔｘ ａ ｇ ｔｇ ｈ ｃ ｒ
｛ （ ｗ） ａ０ ｆ ｕ ＩＴ ∈Ｅ（ ｝ｆ ｕ 表示 染边 Ｕ 的色 ， ． Ｇ） ， （ ｗ） Ｗ 且
参 照文 Ｅｉ ｌ．
定义 １ 对 图 Ｇ（ Ｅ） ｔ 正 整 数 ， ［ ］ Ｖ， ， 是 Ｓ是 ｔ
元集 ， 是 从 （ ＵＥ（ 到 Ｓ的映射 ． Ｇ） Ｇ） 如果
１ ）对 Ｖ ， ∈ Ｅ（ ， 制 Ｇ） “≠ ， ｆ（ ｖ ≠ 有 ｕ） ｆｖ ； （ｗ）
维普资讯
第３ ４卷 第 ２期 ２０ 年 ４月 ０８
Ｅ ）直 积图 ×Ｇ ， ２的顶 点集 为 ， × ， （ ， ） 点 “， ，
与 （ ２ｖ ） “ ，ｚ 相邻 当且 仅 当 Ｕ Ｕ ∈Ｅ１ 一 ∈ 或 １２ ，
者 Ｕ ＝“ ∈Ｖｌ Ｖ ∈Ｅ２ ｌ ２ ， ２ ．
（ Ｃｏｌ ｇ ｆＭ ａ ｈ ｍａ ｉｓａ ｄ Ｉ ｆｒ ｔｏ ｃｅ ｃ ，Ｎｏ ｔ ｗｅ ｔＮｏ ｍａ ｉｅ ｓｔ ｌ ｅｏ ｔ ｅ ｔ ｎ ｎｏ ｍａ ｉｎ Ｓ ｉｎ ｅ ｅ ｃ ｒｈ ｓ ｒ ｌＵｎｖ ｒ ｉ ｙ，Ｌａ ｈ ｕ ￣ ｏ ７ ０ ０，Ｃｈｉａ ３ ０７ ｎ）
ｃ ｌｒｎ ｕ ｅ ｎ Ｃ ｒｅ ｉｎ ｐ ｏ ｕ ｔＧＸ ｏｏ ｉ ｇ ｎ ｍｂ ｒｏ ａ ｔｓａ ｒ ｄ ｃ Ｐ ａ ｄ Ｇ× Ｃ ｗｈ ｒ ｗａ ｔ ｒ ｆｎ ｏ ｅ １ ｎ ｍ， ｅ ｅＧ ｓａｓａ ，ａ ｒｗｈ ｅ．
Ｋｅ ｒ ｓ ａ ｒｅ ｉ ｒ ｄ ｃ ｏ ｒｐ ｓ ｄａｅ ｔｖｒｅ ｉ ｉ ｕｓ ｉｇ ｔｔｌ ｏｏ ｉｇ ｄａｅ ｔｖ ｒｅ ｙ ｗｏ ｄ ：Ｃ ｔｓ ｎ ｐｏ ｕ ｔ ｆ ａ ｈ ；ａｊｃｎ ｅｔｘ ｄｓ ｎ ｉ ｎ ｏａ ｌ ｎ ；ａｊｃｎ ｅｔｘ ａ ｇ ｔｇ ｈ ｃ ｒ
｛ （ ｗ） ａ０ ｆ ｕ ＩＴ ∈Ｅ（ ｝ｆ ｕ 表示 染边 Ｕ 的色 ， ． Ｇ） ， （ ｗ） Ｗ 且
参 照文 Ｅｉ ｌ．
定义 １ 对 图 Ｇ（ Ｅ） ｔ 正 整 数 ， ［ ］ Ｖ， ， 是 Ｓ是 ｔ
元集 ， 是 从 （ ＵＥ（ 到 Ｓ的映射 ． Ｇ） Ｇ） 如果
１ ）对 Ｖ ， ∈ Ｅ（ ， 制 Ｇ） “≠ ， ｆ（ ｖ ≠ 有 ｕ） ｆｖ ； （ｗ）
维普资讯
第３ ４卷 第 ２期 ２０ 年 ４月 ０８
点可区别边色数的一个上界
大度△≥２的任 意图的点可 区别 边 色数 的上 界为
ｌ△． 中未加述及 的术语 和符号 可参见 文［］ ６ 文 ６．
定理 １ 对 任 一最 大 度 为 △ 的 图 Ｇ， △≥ ２ ，
有
ｘ Ｇ）≤ １ △ ． （ ６
Ｇ 的一个 七 点 可区别边 染色 ， 一 简记 为 ｋＶＤ Ｃ． － Ｅ 称
本文 所考虑 的图均 为连通 的、 限 的、 向的 无
简单 图．
（ 互 相 独立 （ 某个 Ｄ ￡ ． Ｄ ＵＡ ） 对 ） 如果 有 实数
ｚ ， … ， Ｏ １ 使 得 对 每 个 １ ｉ ｚ ， ｚ ∈［ ， ） ≤ ≤ ， ， Ｐ （ ） ｚ － （ 一ｚ ） 则 ￡中所 有 事件 都不 发生 Ａｉ ｉ １ ， ， ≤ Ｉ
很 困 难 的 问题 ．
引理 １ （ 般 局 部 引理 ） 虑 （ 型 的坏 ］ 一 考 典
Ａ ∈Ｄ ，
定义 １， 设 Ｇ是 阶数 至少 为 ２的简单 连通 Ｅ 图 ， 是 正 整数 ， ／是 从 Ｖ（ ＵＥ（ 到 ｛ ， ， 足 若 Ｇ） Ｇ） ｌ ２
…
，
七 的一 个映射 ，使 Ｖ“ ， Ｗ∈Ｅ（ （ ≠ ） ｆ ） ｌ Ａ Ｇ） ，
的概 率至少是Ⅱ （ 一ｚ） ． １ ＞Ｏ
ｌ ∈ Ｖ（ ）Ｕ Ｇ ，Ｖ∈ Ｅ（ ｝ 如果 是 ｋ 正 常 边 染色 ， 对 任 意 Ｕ ∈ Ｖ（ ， Ｃ “ ≠ Ｃ ， 么 称 为 图 Ｇ 的 Ｇ）． 一 且 ， Ｇ）有 （ ） （） 那
点 可 区 别边 染 色 （ 称 为 ｋＶ Ｃ ． ｘ Ｇ） ｍｉ｛ Ｇ有 ｋＶＤ Ｃ 称 为 图 Ｇ的点 可 区别 边 色 数 文 通 过 简 － ＤＥ ） 数 （ ： ｎ ｋｌ － Ｅ） 本
图的邻点强可区别全色数的新上界
３
＼●●●●－ 、＼
一
Ａ
２
萨
＼、 ● ● ● ／
２ ２
△
２
—
△
＋
１ ≥ １ ６△ ＋
△
≥
不妨 取 Ｍ ：Ｍ ＝２ ８ ， 则 容易 验证 对 于任 意 Ａ≥２ ， 上述 不等 式成 立
同理 ， 对式（ ２ ） 有：
（ 一 ） 。 （ 一 ） （ 一 ４ ＼ Ｊ ｚ Ａ ｆ Ｉ 卜
究 了 图 的 邻 点 强 可 区别 全 染 色 ， 得 到 了一 个 新 的色 数 上 界 ． 即证 明 了对 任 意 最 大 度 △／ ＞２的 图 Ｇ， Ｘ 。 ≤ ３ ２ Ａ ．
关键 词 ： 图论 ； 概率方法 ； 邻 点 强 可 区 别 全 染 色
中图分类号 ： Ｏ１ ５ ７ ． ５ 文 献标 识 码 ： Ａ 文章 编 号 ： １ ０ ０ ５ — ８ ０ ３ ６ （ ２ ０ １ ３ ） ０ １ － ０ ０ ７ ９ ・ ０ ４
所 以对式 （ １ ） 有：
・
～ ２
≤
（ １ 一
～ 因此证 明 （ １ ） 只需要 证 ：
２
３
（ １ 一
一
一 １
一 ２
＼ 、 ● ● ● ● ，／
≥ （ ÷ ） 尝 ｉ
Ａ
— ４
㈡
Ａ ２
十 ４
Ａ
即证 ：
＼ 、●● ●● ／
）≠
）
）≠， （ “ ）≠， （ ）；
）；
（ ２ ） 对任 意两 相邻 的边 “ ， ｕ ∈ Ｅ（ Ｇ） （ ≠ ） Ｕ Ｗ）≠
（ ３ ） 对任 意 的边 “ Ｅ Ｅ（ Ｇ） ，其 端 点 的 色 集 合 满 足 Ｃ （ “ ）≠ Ｃ（ ） ， 其 中任 一 顶 点 ｕ的 色 集 合 为 Ｃ （ ）＝ ｛ － 厂 （ ） ｝ｕ ｛ ）Ｉ ｕ ∈Ｅ（ Ｇ ） ｝ｕ ｛ “ ）ｌ “ Ｅ Ｅ（ Ｇ ） ｝ ．则称 ，是 Ｇ图的一个 邻 点强 可 区别 的 全染 色法 （ 简记 为 一 Ａ Ｖ Ｓ ＤＴ Ｃ ） ， 且 称数 （ Ｇ ）＝ｍｉ ｎ ｛ ｋ Ｉ ｋ—Ａ Ｖ Ｓ ＤＴ Ｃ｝ 为 Ｇ的邻 点强 可 区别 的全色 数． 引理 １ （ 一般 局部 引理 ） 考虑（ 典 型 的坏 的 ） 事 件集 合 占 ＝ ｛ Ａ ， Ａ ： ， …， Ａ ｝ ， 对 每一个 Ａ （ １≤ ｉ ≤
图论讲义第6章-图的着色问题
| c1 (ν ) | = 1 ，其中 ci (υ ) 表示 υ 阶第 i 类图的集合。这 v →∞ | c (ν ) ∪ c (ν ) | 1 2
vk
… v3 v2
i4 i3 i2
u
… H2
ik i0
…
im ik
i1
vm
v1
v
但是，因 vk 在 H 1 中的度为 2（恰与一条 i0 色边和一条 ik 色边相关联） ，故它在 H 2 中的 。这与 H 2 是奇圈矛盾。 （注意 vk 必在分支 H 2 中，因它与 度为 1（仅与一条 i0 色边相关联） 。由此可知反证法假设不能成立。证毕。 vk－1 有 i0、ik 交错路（ H 1 的一段）相连） 对于有重边的图 G，设 μ (G ) 表示 G 中边的最大重数，Vizing 实际上证明了一个更一般 的结论： Δ (G ) ≤
（其中 v0 点的关联边有可能是同一种色） 。按这 样可得 G*的一个边 2-染色 c = ( E1 , E 2 ) ， 种办法给 G*的边染色后，去掉 v0 及其关联的边，便得到 G 的一个边 2-染色。对于 G 中偶 度点，它关联的边及其颜色与 G*中相同；对 G 的任何奇度点 v，在 G 中比在 G*中少关联一 条边，但只要 d G ( v ) > 1 , 便有 d G ( v ) ≥ 3 , 故由染色的方法知，与 v 点关联的边中两种颜色 的都有。这说明 G 的边 2-染色 c = ( E1 ∩ E (G ), E 2 ∩ E (G )) 即为所求的边 2-染色。证毕。
… H1 vk-1
ikik i0
( Δ + 1) 边染色。由引理 6.1.2， G[ Ei′0 ∪ Ei′k ] 中含有 u 的那个分支 H 1 是个奇圈。
毕业论文范例——mycielski图的染色问题
目录中文摘要------------------------------------------------------------------2 英文摘要------------------------------------------------------------------3 引言----------------------------------------------------------------------4 一、mycielski图的定义-----------------------------------------------------5 1． mycielski图的定义----------------------------------------------------52 . 广义mycielski图的定义-----------------------------------------------5二、mycielski图的染色问题-------------------------------------------------5(一)边色数----------------------------------------------------------------51. Mycielski图的边色数---------------------------------------------------52.广义Myc ielski 图的边色数----------------------------------------------6(二)邻强边色数------------------------------------------------------------61. Myciel ski 图的邻强边色数---------------------------------------------72. 广义Mycielski 图的邻强边色数------------------------------------------7 （三）全色数--------------------------------------------------------------81. Mycielski图的全色数--------------------------------------------------82. 广义Mycielski图的全色数---------------------------------------------9 （四）邻点可区别全色数----------------------------------------------------91.Mycielski 图的邻点可区别全色数---------------------------------------102.广义Mycielski图的邻点可区别全色数----------------------------------12 致谢--------------------------------------------------------------------13 参考文献----------------------------------------------------------------14Mycielski图的染色问题摘要：本论文总结了Mycielski 图及广义Mycielski 图关于染色问题的各方面定义和定理，主要包括边色数、邻强边色数、全色数、邻点可区别全色数的相关结论。
若干图的倍图的邻点可区别边_全_染色_何雪
Adjacent vertex-distinguishing edge / total colorings of double graph of some graphs
HE Xue，TIAN Shuangliang *
（ School of M athematics and Computer Science，Northw est University for Nationalities，Lanzhou 730030 ，Gansu，China） Abstract： Let G be a simple graph w ith vertex set V （ G ） and edge set E （ G ） ． An edgecoloring σ of G is called an adjacent vertex distinguishing edgecoloring of G if C σ （ u） ≠C σ （ v ） for any uv ∈E（ G ） ，w here C σ （ u） denotes the set of colors of edges incident w ith u． A totalcoloring σ of G is called an adjacent vertex distinguishing totalcoloring of G if S σ （ u） ≠S σ （ v ） for any uv ∈E（ G ） ，w here S σ （ u） denotes the set of colors of edges incident w ith u together w ith the color assigned to u． The minimum number of colors required for an adjacent vertexdistinguishing edgecoloring （ resp． totalcoloring ） of G is called adjacent vertexdistinguishing edge （ resp． total ） chromatic number，and denoted by χ' as （ G ） （ resp． χ at （ G ） ） ． The upper bounds for these parameters of the double graph D （ G ） of graph G are given in this paper． Specifically ，the exact value of these parameters for the double graph of complete graphs and trees are determined． Key words： double graph； adjacent vertexdistinguishing edge coloring ； adjacent vertexdistinguishing total coloring
图的距离不大于2的点可区别的边色数的一个新的上界
） 表 示 ２个顶 点 Ｕ 、 之 问 的最 短距 离 。 当 一１时 ，
色数 的 一 个 上 界 ； 文献 ［ ４ ］简 单 图 Ｇ， △≥ １ ０ 加，
（ Ｇ） ＜△ ＋３ ０ ０ ； ２ ０ ０ ６年 ， 张忠辅等人［ ］ 提 出 图 的 距离 不 大 于 的 任 意两 点 可 区别 边 染 色 ， 也 可 以称
的一 个 ａ —Ｄ（ ． ８ ） 一点 可 区别 的边 染 色 ， 简记为 ａ —
Ｄ（ １ ｆ ） －Ｖ ＤＰＥ Ｃ， 对 一 个 图进 行 ａ —Ｄ（ ） 一点 可 区
别边 染 色时 所需 要 的最小 ａ称 为 图 Ｇ 的 Ｄ（ ） 一点 可 区别边 染 色 的边 色 数 ， 记 为 （ Ｇ） ， 其中 ｄ （ ，
文章编号 ： １ ６ ７ １ ４ ６ ７ ９ （ ２ ０ １ ３ ） ０ １ — ０ ０ ７ ５ — ０ ３
Ｏｎ ｅ ｎ ｅ ｗ ｕ ｐ ｐ ｅ ｒ ｂ ｏ ｕ ｎ ｄ ｏ ｎ ｔ ｈ ｅ Ｄ（ ２ ） － ｖ ｅ ｒ ｔ ｅ ｘ — ｄ ｉ ｓ ｔ ｉ ｎ ｇ ｕ ｉ ｓ ｈ ｉ ｎｉ ｎ ｇ
］ ≥ ３ ＇ ｗ ｈ ｉ ｃ ｝ １ ｉ ｓ ｂ ｅ ｔ ｔ ｅ ｒ ｔ ｈ ａ ｎ ｔ ｈ ｅ ｒ ｅ ｓ ｕ ｈ ｓ Ｏ ｆ ｔ ｈ ｅ ｐ ａ ｐ ｅ ｒ ［ ６ ］ ．
Ｋｅ ｙ ｗｏ ｒ ｄ ｓ ：ｇ ｒ ａ ｐ ｈ； ｆ ｉ ｒ ｓ ｔ ｍｏ ｍｅ ｎ ｔ ｐ ｒ ｉ ｎ ｃ ｉ ｐ ｌ ｅ ；Ｍ ａ ｒ ｋ ｏ ｖ ｉ ｎ ｅ ｑ ｕ ａ ｌ ｉ ｔ ｙ； Ｄ （２） ｖ ｅ ｒ ｔ ｅ ｘ － ｄ ｉ ｓ ｔ ｉ ｎ ｇ ｕ ｉ ｓ ｈ ｉ ｎ ｇ ｐ ｒ ｏ ｐ ｅ ｒ
第２ ７ 卷第 １ 期
２ ０ １ ３年 ３月
色数 的 一 个 上 界 ； 文献 ［ ４ ］简 单 图 Ｇ， △≥ １ ０ 加，
（ Ｇ） ＜△ ＋３ ０ ０ ； ２ ０ ０ ６年 ， 张忠辅等人［ ］ 提 出 图 的 距离 不 大 于 的 任 意两 点 可 区别 边 染 色 ， 也 可 以称
的一 个 ａ —Ｄ（ ． ８ ） 一点 可 区别 的边 染 色 ， 简记为 ａ —
Ｄ（ １ ｆ ） －Ｖ ＤＰＥ Ｃ， 对 一 个 图进 行 ａ —Ｄ（ ） 一点 可 区
别边 染 色时 所需 要 的最小 ａ称 为 图 Ｇ 的 Ｄ（ ） 一点 可 区别边 染 色 的边 色 数 ， 记 为 （ Ｇ） ， 其中 ｄ （ ，
文章编号 ： １ ６ ７ １ ４ ６ ７ ９ （ ２ ０ １ ３ ） ０ １ — ０ ０ ７ ５ — ０ ３
Ｏｎ ｅ ｎ ｅ ｗ ｕ ｐ ｐ ｅ ｒ ｂ ｏ ｕ ｎ ｄ ｏ ｎ ｔ ｈ ｅ Ｄ（ ２ ） － ｖ ｅ ｒ ｔ ｅ ｘ — ｄ ｉ ｓ ｔ ｉ ｎ ｇ ｕ ｉ ｓ ｈ ｉ ｎｉ ｎ ｇ
］ ≥ ３ ＇ ｗ ｈ ｉ ｃ ｝ １ ｉ ｓ ｂ ｅ ｔ ｔ ｅ ｒ ｔ ｈ ａ ｎ ｔ ｈ ｅ ｒ ｅ ｓ ｕ ｈ ｓ Ｏ ｆ ｔ ｈ ｅ ｐ ａ ｐ ｅ ｒ ［ ６ ］ ．
Ｋｅ ｙ ｗｏ ｒ ｄ ｓ ：ｇ ｒ ａ ｐ ｈ； ｆ ｉ ｒ ｓ ｔ ｍｏ ｍｅ ｎ ｔ ｐ ｒ ｉ ｎ ｃ ｉ ｐ ｌ ｅ ；Ｍ ａ ｒ ｋ ｏ ｖ ｉ ｎ ｅ ｑ ｕ ａ ｌ ｉ ｔ ｙ； Ｄ （２） ｖ ｅ ｒ ｔ ｅ ｘ － ｄ ｉ ｓ ｔ ｉ ｎ ｇ ｕ ｉ ｓ ｈ ｉ ｎ ｇ ｐ ｒ ｏ ｐ ｅ ｒ
第２ ７ 卷第 １ 期
２ ０ １ ３年 ３月
最大度为6的图G的邻点可区别边色数的一个上界
最大度为6的图G的邻点可区别边色数的一个上界吴燕青【摘要】本文研究了最大度为6的图G的邻点可区别边着色问题.利用反证法,得到了最大度为6的非半正则图G的邻点可区别边色数的一个上界.【期刊名称】《数学杂志》【年(卷),期】2019(039)001【总页数】11页(P42-52)【关键词】最大度;邻点可区别边着色;邻点可区别边色数【作者】吴燕青【作者单位】山西师范大学数学与计算机科学学院,山西临汾 041000【正文语种】中文【中图分类】O157.51 引言本文主要考虑不含孤立边的有限简单图.对图G,用V(G),E(G),∆(G)和mad(G)分别表示图G的顶点集,边集,最大度和最大平均度.在G中,用NG(v)表示顶点v的邻集.度为k的顶点称为k-顶点.度至少为(至多为)k的顶点称为k+-顶点(k−-顶点).用di(v)表示与顶点v相邻的i-顶点的数目.一个图G称为半正则的,如果它的每一条边至少和一个最大度顶点相关联.否则,称为非半正则的.一个图G的正常边着色是一个映射φ:E(G)→{1,···,k},使得每一对相邻边e1和e2,有φ(e1)φ(e2).用cφ(v)表示在着色φ下与v相关联的边所着的颜色组成的集合.一个图G的正常边着色φ称为邻点可区别边着色,如果G的任何相邻顶点u和v,满足cφ(u)cφ(v).G的邻点可区别边色数是使得G有一个k-邻点可区别边着色的最少颜色数k.在2002年,文献[1]首先讨论了邻点可区别边着色问题,并提出了以下猜想.猜想设图G为顶点数至少为3的连通图且GG5,则.对于一般图G,文献[2]给出了若∆(G)>1020,则.文献[3]给出了.文献[4]给出了.文献[5]给出了若∆(G)≤3,则.文献[6]给出了若∆(G)≤5且,则.文献[7]给出了若∆(G)≤4,则,和若∆(G)≤5,则.本文证明了若G是一个最大度为6的非半正则图,则.引理1.1 [7]假设G是一个∆(G)≥2的半正则图.若∆(G)≡0(mod 3),则.2 主要结果定理2.1 设G是一个最大度为6的非半正则图,则.证假设G是含边数最少的连通的极小反例.由于G是非半正则的,所以存在uv∈E(G),使得dG(u)≤5且dG(v)≤5.不妨设dH(u)≤dH(v).设H=G−uv,由G的极小性可知,H有一个12-邻点可区别边着色φ,它用的颜色集C={1,2,···,12}.为了叙述起来方便,称在φ下边e对颜色α是允许的,若在φ下用颜色α给边e重新着色可得H的一个新的12-邻点可区别边着色.用L(e)表示在φ下由边e的所有允许的颜色组成的集.设xy∈E(H),且dG(x)=dG(y).若颜色β∈cφ(y)\cφ(x),且|cφ(y)∩cφ(x)|=dH(x)=dH(y)−1,则称在φ下颜色β为顶点x的不法颜色.用Ax表示在φ下顶点x的所有不法颜色组成的集.设Ωz(x)={cφ(y)|y∈NH(x)\{z}}(或Ω(x)={cφ(y)|y∈NH(x)}).由uv的选择可知dH(u)+dH(v)≤8.情形1 假设dH(u)+dH(v)≤6.情形1.1 假设dH(u)=0.由uv的选择和G的假设可知1≤dH(v)≤4.显然,存在p∈C\cφ(v),用p给uv着色可得G的一个12-邻点可区别边着色,矛盾.情形1.2 假设dH(u)=1且u0∈NH(u).由uv的选择可知1≤dH(v)≤4.假设dH(v)=1且v0∈NH(v).若φ(vv0)6φ(uu0),显然,存在p∈C\{cφ(v)∪cφ(u)},用p给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,φ(vv0)=φ(uu0).由于|L(vv0)|≥1,所以存在q∈L(vv0).现用q给vv0重新着色可得H的一个12-邻点可区别边着色φ0.从而φ0(vv0)φ0(uu0),正如前面已讨论,矛盾.假设2≤dH(v)≤4.显然,存在p∈C\{cφ(v)∪cφ(u)},用p给uv着色可得G的一个12-邻点可区别边着色,矛盾.情形1.3 假设dH(u)=2且uj∈NH(u),其中j=1,2.由uv的选择可知2≤dH(v)≤4.假设dH(v)=2且vj∈NH(v),其中j=1,2. 若|cφ(u)∩cφ(v)|≤1,显然,存在p∈C\{cφ(v)∪cφ(u)},用p给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,|cφ(u)∩cφ(v)|=2.不妨设φ(vv1)=1和φ(vv2)=2.在H中,若v的邻点有一个5−-顶点,不妨设dH(v1)≤5.由于|L(vv1)|≥1,所以存在p∈L(vv1).现用p给vv1重新着色可得H的一个12-邻点可区别边着色φ0.从而|cφ0(u)∩cφ0(v)|=1,正如前面已讨论,矛盾.否则,v1和v2均是6-顶点.设v1j∈NH(v1),其中j=1,2,3,4,5.若2∈cφ(v1),因而|L(vv1)|≥1,所以存在p∈L(vv1).现用p给vv1重新着色可得H的一个12-邻点可区别边着色φ0.从而|cφ0(u)∩cφ0(v)|=1,正如前面已讨论,矛盾.否则,2cφ(v1).不妨设φ(v1v1j)=j+2,其中j=1,2,3,4,5.若存在q∈C\{cφ(v)∪cφ(v1)},用q给vv1重新着色可得H的一个12-邻点可区别边着色φ0,从而|cφ0(u)∩cφ0(v)|=1,正如前面已讨论,矛盾.否则,不妨设cφ(v11)={3,4,5,6,7,8},cφ(v12)={3,4,5,6,7,9},cφ(v13)={3,4,5,6,7,10},cφ(v14)={3 ,4,5,6,7,11}和cφ(v15)={3,4,5,6,7,12}. 若存在r∈{1,2},使得{r,4,5,6,7,8}Ωv1(v11),那么用r和3分别给v1v11和vv1重新着色可得H的一个12-邻点可区别边着色φ0.从而|cφ0(u)∩cφ0(v)|=1,正如前面已讨论,矛盾.否则,在φ下,{{1,4,5,6,7,8},{2,4,5,6,7,8}}⊆Ωv1(v11).由于|Ωv1(v11)|=5,所以存在s∈{9,10,11,12},使得{s,4,5,6,7,8}Ωv1(v11).现用s和t∈{9,10,11,12}\{s},分别给v1v11和vv1重新着色可得H的一个12-邻点可区别边着色φ0.从而|cφ0(u)∩cφ0(v)|=1,正如前面已讨论,矛盾.假设3≤dH(v)≤4.由前面的讨论可知,uj均是4+-顶点,其中j=1,2.显然,存在p∈C\{cφ(v)∪cφ(u)},用p给uv着色可得G的一个12-邻点可区别边着色,矛盾. 情形1.4 假设dH(u)=3.因而dH(v)=3.设vj∈N H(v),其中j=1,2,3.假设|cφ(u)∩cφ(v)|=0.若存在p∈C\{cφ(v)∪cφ(u)},用p给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,在φ下,{{p}∪cφ(v)}∈Ω(v),或{{p}∪cφ(u)}∈Ω(u).由于|L(vv1)|≥5,所以存在q∈L(vv1)\{cφ(v2)∪cφ(v3)}.现用q 给vv1重新着色,用φ(vv1)给uv着色可得G的一个12-邻点可区别边着色,矛盾. 假设1≤|cφ(u)∩cφ(v)|≤2.显然,存在p∈C\{cφ(v)∪cφ(u)},用p给uv着色可得G 的一个12-邻点可区别边着色,矛盾.假设|cφ(u)∩cφ(v)|=3.不妨设φ(vvj)=j,其中j=1,2,3.在H中,假设v的邻点中有一个5−-顶点.不妨设d(v1)≤5.由情形1.3可知,v2和v3均不是3-顶点.显然,|L(vv1)|≥1,所以存在p∈L(vv1),用p给vv1重新着色可得H 的一个12-邻点可区别边着色φ0.从而|cφ0(u)∩cφ0(v)|=2,正如前面已讨论,矛盾. 在H中,假设v的邻点均是6-顶点.设v1j∈NH(v1),其中j=1,2,3,4,5.假设|{2,3}∩cφ(v1)|=0.不妨设φ(v1v1j)=j+3,其中j=1,2,3,4,5.若存在p∈C\{cφ(v)∪cφ(v1)},用p给vv1重新着色可得H的一个12-邻点可区别边着色φ0,从而|cφ0(u)∩cφ0(v)|=2,正如前面已讨论,矛盾.否则,不妨设cφ(v11)={4,5,6,7,8,9},cφ(v12)={4,5,6,7,8,10},cφ(v13)={4,5,6,7,8,11}和cφ(v14)={4,5,6,7,8,12}. 若存在q∈{1,2,3},使得{q,5,6,7,8,9}Ωv1(v11),那么先用q 给v1v11重新着色.进一步,若用4给vv1重新着色可得H的一个12-邻点可区别边着色,从而|cφ0(u)∩cφ0(v)|=2,正如前面已讨论,矛盾.否则,cφ(v15)={q,4,5,6,7,8}.现用10给vv1重新着色可得H的一个12-邻点可区别边着色φ00.从而|cφ00(u)∩cφ00(v)|=2,正如前面已讨论,矛盾.否则,在φ下,{{1,5,6,7,8,9},{2,5,6,7,8,9},{3,5,6,7,8,9}}⊆Ωv1(v11).由于|Ωv1(v11)|=5,所以存在r∈{10,11,12},使得{r,5,6,7,8,9}Ωv1(v11).若用r和s∈{10,11,12}\{r}分别给v1v11和vv1重新着色可得H的一个12-邻点可区别边着色φ0,从而|cφ0(u)∩cφ0(v)|=2,正如前面已讨论,矛盾.否则,cφ(v5)={r,s,5,6,7,8}.现用r和t∈{10,11,12}\{r,s}分别给v1v11和vv1重新着色可得H的一个12-邻点可区别边着色φ00.从而|cφ00(u)∩cφ00(v)|=2,正如前面已讨论,矛盾.假设|{2,3}∩cφ(v1)|=1.不妨设φ(v1v11)=2,φ(v1v1j)=j+2,其中j=2,3,4,5.若存在p∈C\{cφ(v)∪cφ(v1)},用p给vv1重新着色可得H的一个12-邻点可区别边着色φ0,从而|cφ0(u)∩cφ0(v)|=2,正如前面已讨论,矛盾.否则,不妨设cφ(v11)={2,4,5,6,7,8},cφ(v12)={2,4,5,6,7,9},cφ(v13)={2,4,5,6,7,10},cφ(v14)={2 ,4,5,6,7,11}和cφ(v15)={2,4,5,6,7,12}.若存在q∈{1,3},使得{q,2,5,6,7,9}Ωv1(v12),那么用q和4分别给v1v12和vv1重新着色可得H的一个12-邻点可区别边着色φ0.从而|cφ0(u)∩cφ0(v)|=2,正如前面已讨论,矛盾.否则,在φ下,{{1,2,5,6,7,9},{2,3,5,6,7,9}}⊆Ωv1(v12).由于|Ωv1(v12)|=5,所以存在r∈{8,10,11,12},使得{r,2,5,6,7,9}Ωv1(v12).现用r和s∈{8,10,11,12}\{r}分别给v1v12和vv1重新着色可得H的一个12-邻点可区别边着色φ0.从而|cφ0(u)∩cφ0(v)|=2,正如前面已讨论,矛盾.假设|{2,3}∩cφ(v1)|=2.由于|L(vv1)|≥1,所以存在p∈L(vv1).现用p给vv1重新着色可得H的一个12-邻点可区别边着色φ0,从而|cφ0(u)∩cφ0(v)|=2,正如前面已讨论,矛盾.情形2 假设dH(u)+dH(v)=7.由uv的选择可知dH(u)=3且dH(v)=4.设uj∈NH(u),其中j=1,2,3.由情形1可知,uj均为5+-顶点,其中j=1,2,3.因此存在p∈C\{cφ(u)∪cφ(v)},用p给uv着色可得G的一个12-邻点可区别边着色,矛盾.情形3 假设dH(u)+dH(v)=8.由uv的选择可知dH(u)=4且dH(v)=4.设vi∈NH(v),其中i=1,2,3,4.在φ下,不妨设φ(vvi)=i,其中i=1,2,3,4.设uj∈NH(u),其中j=1,2,3,4.由情形1和2可知,在H中,与u相邻的顶点和与v相邻的顶点均是5+-顶点.情形3.1 假设dH(uj)=6,其中j=1,2,3,4.情形3.1.1 假设|cφ(u)∩cφ(v)|=0.设φ(uuj)=j+4,其中j=1,2,3,4.若存在p∈C\{cφ(u)∪cφ(v)},用p给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,在φ下,{{p}∪cφ(v)}∈Ω(v). 显然,C\{cφ(v)∪cφ(u)}={9,10,11,12}. 不妨设cφ(v1)={1,2,3,4,9},cφ(v2)={1,2,3,4,10},cφ(v3)={1,2,3,4,11}和cφ(v4)={1,2,3,4,12}. 若存在q∈{5,6,7,8},使得{q,2,3,4,9}Ωv(v1),那么用q给vv1重新着色,用1给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,在φ下,Ωv(v1)={{2,3,4,5,9},{2,3,4,6,9},{2,3,4,7,9},{2,3,4,8,9}}.现用10给vv1重新着色,用11给uv着色可得G的一个12-邻点可区别边着色,矛盾.情形3.1.2 假设1≤|cφ(u)∩cφ(v)|≤3.显然,存在p∈C\{cφ(u)∪cφ(v)},用p给uv 着色可得G的一个12-邻点可区别边着色,矛盾.情形3.1.3 假设|cφ(u)∩cφ(v)|=4.在H中,假设d6(v)=4.因此d(vi)=6,其中i=1,2,3,4.设v1j∈NH(v1)\{v},其中j=1,2,3,4,5.假设|{2,3,4}∩cφ(v1)|=0.不妨设φ(v1v1j)=j+4,其中j=1,2,3,4,5.若存在p∈C\{cφ(v)∪cφ(v1)},用p给vv1重新着色可得H的一个12-邻点可区别边着色φ0,从而|cφ0(u)∩cφ0(v)|=3,正如情形3.1.2,矛盾.否则,不妨设cφ(v11)={5,6,7,8,9,10},cφ(v12)={5,6,7,8,9,11}和cφ(v13)={5,6,7,8,9,12}.若存在q∈{1,2,3,4},使得{q,6,7,8,9,10}/∈Ωv1(v11),那么先用q给v1v11重新着色.进一步,若用5给vv1重新着色可得H的一个12-邻点可区别边着色φ0,从而|cφ0(u)∩cφ0(v)|=3,正如情形3.1.2,矛盾.否则,cφ(v14)={q,5,6,7,8,9},或cφ(v15)={q,5,6,7,8,9}. 不妨设cφ(v14)={q,5,6,7,8,9}. 若用11给vv1重新着色可得H的一个12-邻点可区别边着色φ00,从而|cφ00(u)∩cφ00(v)|=3,正如情形3.1.2,矛盾.否则,cφ(v15)={q,6,7,8,9,11}.现用12给vv1重新着色可得H的一个12-邻点可区别边着色φ000.从而|cφ000(u)∩cφ000(v)|=3,正如情形3.1.2,矛盾.否则,在φ下,{{1,6,7,8,9,10},{2,6,7,8,9,10},{3,6,7,8,9,10},{4,6,7,8,9,10}}⊆Ωv1(v11).类似的,{{1,5,7,8,9,11},{2,5,7,8,9,11},{3,5,7,8,9,11},{4,5,7,8,9,11}}⊆Ωv1(v12).由于|Ωv1(v1j)|=5,其中j=1,2,所以存在r∈{11,12},不妨设r=11,使得{6,7,8,9,10,11}/∈Ωv1(v11),存在s∈{10,12},使得{s,5,7,8,9,11}Ωv1(v12).若用11和12分别给v1v11和vv1重新着色可得H的一个12-邻点可区别边着色φ0,从而|cφ0(u)∩cφ0(v)|=3,正如情形3.1.2,矛盾.否则,cφ(v14)={6,7,8,9,11,12},或cφ(v15)={6,7,8,9,11,12}.不妨设cφ(v14)={6,7,8,9,11,12}.若用s和t∈{10,12}\{s}分别给v1v12和vv1重新着色可得H的一个12-邻点可区别边着色φ00,从而|cφ00(u)∩cφ00(v)|=3,正如情形3.1.2,矛盾.否则,cφ(v15)={5,7,8,9,10,12}.现用11,s和t分别给v1v11,v1v12和vv1重新着色可得H的一个12-邻点可区别边着色φ000.从而|cφ000(u)∩cφ000(v)|=3,正如情形3.1.2,矛盾.假设|{2,3,4}∩cφ(v1)|=1.不妨设φ(v1v11)=2和φ(v1v1j)=j+3,其中j=2,3,4,5.若存在p∈C\{cφ(v)∪cφ(v1)},用p给vv1重新着色可得H的一个12-邻点可区别边着色φ0,从而|cφ0(u)∩cφ0(v)|=3,正如情形3.1.2,矛盾. 否则,不妨设cφ(v11)={2,5,6,7,8,9},cφ(v12)={2,5,6,7,8,10},cφ(v13)={2,5,6,7,8,11}和cφ(v14)={2,5,6,7,8,12}. 若存在q∈{1,3,4},使得{q,2,6,7,8,10}Ωv1(v12),那么先用q给v1v12重新着色.进一步,若用5给vv1重新着色可得H的一个12-邻点可区别边着色φ0,从而|cφ0(u)∩cφ0(v)|=3,正如情形3.1.2,矛盾.否则,cφ(v15)={q,2,5,6,7,8}.现用11给vv1重新着色可得H的一个12-邻点可区别边着色φ00.从而|cφ00(u)∩cφ00(v)|=3,正如情形3.1.2,矛盾.否则,在φ下,{{1,2,6,7,8,10},{2,3,6,7,8,10},{2,4,6,7,8,10}}⊆Ωv1(v12).由于|Ωv1(v12)|=5,所以存在r∈{9,11,12},使得{r,2,6,7,8,10}Ωv1(v12),那么先用r给v1v12重新着色.进一步,若用s∈{9,11,12}\{r}给vv1重新着色可得H的一个12-邻点可区别边着色φ0,从而|cφ0(u)∩cφ0(v)|=3,正如情形3.1.2,矛盾. 否则,cφ(v15)={r,s,2,6,7,8}. 现用t∈{9,11,12}\{r,s}给vv1重新着色可得H的一个12-邻点可区别边着色φ00.从而|cφ00(u)∩cφ00(v)|=3,正如情形3.1.2,矛盾.假设|{2,3,4}∩cφ(v1)|=2.不妨设φ(v1v11)=2,φ(v1v12)=3和φ(v1v1j)=j+2,其中j=3,4,5.若存在p∈C\{cφ(v)∪cφ(v1)},用p给vv1重新着色可得H的一个12-邻点可区别边着色φ0,从而|cφ0(u)∩cφ0(v)|=3,正如情形3.1.2,矛盾.否则,不妨设cφ(v11)={2,3,5,6,7,8},cφ(v12)={2,3,5,6,7,9},cφ(v13)={2,3,5,6,7,10},cφ(v14)={2 ,3,5,6,7,11}和cφ(v15)={2,3,5,6,7,12}.若存在q∈{1,4},使得{q,2,3,6,7,10}/∈Ωv1(v13),那么用q和5分别给v1v13和vv1重新着色可得H的一个12-邻点可区别边着色φ0.从而|cφ0(u)∩cφ0(v)|=3,正如情形3.1.2,矛盾.否则,在φ下,{{1,2,3,6,7,10},{2,3,4,6,7,10}}⊆Ωv1(v13).由于|Ωv1(v13)|=5,所以存在r∈{8,9,11,12},使得{r,2,3,6,7,10}Ωv1(v13).现用r和s∈{8,9,11,12}\{r}分别给v1v13和vv1重新着色可得H的一个12-邻点可区别边着色φ0,从而|cφ0(u)∩cφ0(v)|=3,正如情形3.1.2,矛盾.假设|{2,3,4}∩cφ(v1)|=3.由于|L(vv1)|≥1,所以存在p∈L(vv1).现用p给vv1重新着色可得H的一个12-邻点可区别边着色φ0.从而|cφ0(u)∩cφ0(v)|=3,正如情形3.1.2,矛盾.在H中,假设d6(v)≤3.不妨设d(v1)=5.若|{2,3,4}∩cφ(v1)|≥1,因而|L(vv1)|≥1,所以存在p∈L(vv1).现用p给vv1重新着色可得H的一个12-邻点可区别边着色φ0.从而|cφ0(u)∩cφ0(v)|=3,正如情形3.1.2,矛盾.否则,|{2,3,4}∩cφ(v1)|=0.不妨设φ(v1v1j)=j+4,其中j=1,2,3,4.若存在q∈C\{cφ(v)∪cφ(v1)},用q给vv1重新着色可得H的一个12-邻点可区别边着色φ0,从而|cφ0(u)∩cφ0(v)|=3,正如情形3.1.2,矛盾.否则,不妨设cφ(v11)={5,6,7,8,9},cφ(v12)={5,6,7,8,10},cφ(v13)={5,6,7,8,11}和cφ(v14)={5,6,7,8,12}. 若存在r∈{1,2,3,4},使得{r,6,7,8,9}Ωv1(v11),那么用r和5分别给v1v11和vv1重新着色可得H的一个12-邻点可区别边着色φ0.从而|cφ0(u)∩cφ0(v)|=3,正如情形3.1.2,矛盾.否则,在φ下,Ωv1(v11)={{1,6,7,8,9},{2,6,7,8,9},{3,6,7,8,9},{4,6,7,8,9}}.现用10和11分别给v1v11和vv1重新着色可得H的一个12-邻点可区别边着色φ0.从而|cφ0(u)∩cφ0(v)|=3,正如情形3.1.2,矛盾.情形3.2 假设dH(u1)=5,且d(uj)=6,其中j=2,3,4.情形3.2.1 假设|cφ(u)∩cφ(v)|=0.不妨设φ(uuj)=j+4,j=1,2,3,4.若存在p∈C\{cφ(v)∪cφ(u)},用p给uv着色可得G 的一个12-邻点可区别边着色,矛盾.否则,在φ下,{{p}∪cφ(v)}∈Ω(v),或{{p}∪cφ(u)}∈Ω(u).显然,C\{cφ(v)∪cφ(u)}={9,10,11,12}.假设|Av∩{9,10,11,12}|=4. 不妨设cφ(v1)={1,2,3,4,9},cφ(v2)={1,2,3,4,10},cφ(v3)={1,2,3,4,11}和cφ(v4)={1,2,3,4,12}.若存在q∈{5,6,7,8},使得{q,2,3,4,9}Ωv(v1),那么先用q给vv1重新着色.进一步,若用1给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,cφ(u1)={1,5,6,7,8}.现用10给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,在φ下,Ωv(v1)={{2,3,4,5,9},{2,3,4,6,9},{2,3,4,7,9},{2,3,4,8,9}}.先用10给vv1重新着色.进一步,若用11给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,cφ(u1)={5,6,7,8,11}.现用12给uv着色可得G的一个12-邻点可区别边着色,矛盾.假设|Av∩{9,10,11,12}|=3. 因而|Au∩{9,10,11,12}|=1. 不妨设cφ(v1)={1,2,3,4,9},cφ(v2)={1,2,3,4,10},cφ(v3)={1,2,3,4,11}和cφ(u1)={5,6,7,8,12}.由于|L(uu1)|≥3,所以存在q∈L(uu1).若用q给uu1重新着色,用5给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,cφ(v4)={1,2,3,4,5}.由于|Ωv(v1)|=4,所以存在r∈{5,6,7,8,12},使得{r,2,3,4,9}Ωv(v1).现用r给vv1重新着色,用10给uv着色可得G的一个12-邻点可区别边着色,矛盾.情形3.2.2 假设|cφ(u)∩cφ(v)|=1. 不妨设φ(uu1)=1和φ(uuj)=j+3,其中j=2,3,4.若存在p∈C\{cφ(v)∪cφ(u)},用p给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,在φ下,{{p}∪cφ(v)}∈Ω(v)或{{p}∪cφ(u)}∈Ω(u).显然,C\{cφ(v)∪cφ(u)}={8,9,10,11,12}. 不妨设cφ(v1)={1,2,3,4,8},cφ(v2)={1,2,3,4,9},cφ(v3)={1,2,3,4,10},cφ(v4)={1,2,3,4,11}和cφ(u1)={1,5,6,7,12}. 若存在q∈{5,6,7,12},使得{q,1,3,4,9}Ωv(v2),那么用q给vv2重新着色,用2给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,在φ下,Ωv(v2)={{1,3,4,5,9},{1,3,4,6,9},{1,3,4,7,9},{1,3,4,9,12}}.现用10给vv2重新着色,用11给uv着色可得G的一个12-邻点可区别边着色,矛盾.情形3.2.3 假设2≤|cφ(u)∩cφ(v)|≤3.显然,存在p∈C\{cφ(v)∪cφ(u)},用p给uv 着色可得G的一个12-邻点可区别边着色,矛盾.情形3.2.4 假设|cφ(u)∩cφ(v)|=4.设φ(uuj)=j,其中j=1,2,3,4.假设|{2,3,4}∩cφ(u1)|≥1.由于|L(uu1)|≥1,所以存在p∈L(uu1).现用p给uu1重新着色可得H的一个12-邻点可区别边着色φ0.从而|cφ0(u)∩cφ0(v)|=3,正如情形3.2.3,矛盾.假设|{2,3,4}∩cφ(u1)|=0.设u1j∈NH(u1)\{u},其中j=1,2,3,4.不妨设φ(u1u1j)=j+4,其中j=1,2,3,4.若存在q∈C\{cφ(u)∪cφ(u1)},用q给uu1重新着色可得H的一个12-邻点可区别边着色φ0,从而|cφ0(u)∩cφ0(v)|=3,正如情形3.2.3,矛盾.否则,不妨设cφ(u11)={5,6,7,8,9},cφ(u12)={5,6,7,8,10},cφ(u13)={5,6,7,8,11}和cφ(u14)={5,6,7,8,12}.若存在r∈{1,2,3,4},使得{r,6,7,8,9}Ωu1(u11),那么用r和5分别给u1u11和uu1重新着色可得H的一个12-邻点可区别边着色φ0.从而|cφ0(u)∩cφ0(v)|=3,正如情形3.2.3,矛盾.否则,在φ下,Ωu1(u11)={{1,6,7,8,9},{2,6,7,8,9},{3,6,7,8,9},{4,6,7,8,9}}.现用10和11分别给u1u11和uu1重新着色可得H的一个12-邻点可区别边着色φ0.从而|cφ0(u)∩cφ0(v)|=3,正如情形3.2.3,矛盾.情形3.3 假设dH(u1)=dH(u2)=5且dH(u3)=dH(u4)=6.情形3.3.1 假设|cφ(u)∩cφ(v)|=0.不妨设φ(uuj)=j+4,j=1,2,3,4.若存在p∈C\{cφ(v)∪cφ(u)},用p给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,在φ下,{{p}∪cφ(v)}∈Ω(v),或{{p}∪cφ(u)}∈Ω(u).显然,C\{cφ(v)∪cφ(u)}={9,10,11,12}.假设|Av∩{9,10,11,12}|=4. 不妨设cφ(v1)={1,2,3,4,9},cφ(v2)={1,2,3,4,10},cφ(v3)={1,2,3,4,11}和cφ(v4)={1,2,3,4,12}.若存在q∈{5,6,7,8},使得{q,2,3,4,9}/∈Ωv(v1),那么先用q给vv1重新着色.进一步,若用1给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,cφ(u1)={1,5,6,7,8}或cφ(u2)={1,5,6,7,8}.不妨设cφ(u1)={1,5,6,7,8}.若用10给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,cφ(u2)={5,6,7,8,10}.现用11给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,在φ下,Ωv(v1)={{2,3,4,5,9},{2,3,4,6,9},{2,3,4,7,9},{2,3,4,8,9}}.类似的,Ωv(v2)={{1,3,4,5,10},{1,3,4,6,10},{1,3,4,7,10},{1,3,4,8,10}}.先用10和11分别给vv1和vv2重新着色.进一步,若用2给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,cφ(u1)={2,5,6,7,8}或cφ(u2)={2,5,6,7,8}. 不妨设cφ(u1)={2,5,6,7,8}. 若用 9给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,cφ(u2)={5,6,7,8,9}.现用12给uv着色可得G的一个12-邻点可区别边着色,矛盾.假设|Av∩{9,10,11,12}|=3. 因而|Au∩{9,10,11,12}|≥1. 不妨设cφ(v1)={1,2,3,4,9},cφ(v2)={1,2,3,4,10},cφ(v3)={1,2,3,4,11}和cφ(u1)={5,6,7,8,12}.由于|L(uu1)|≥3,所以存在q∈L(uu1).若用q给uu1重新着色,用5给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,cφ(u2)={q,5,6,7,8}或cφ(v4)={1,2,3,4,5}.若cφ(v4)={1,2,3,4,5},显然,存在r∈{5,6,7,8,12},使得{r,2,3,4,9}Ωv(v1),那么先用r给vv1重新着色.进一步,若用10给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,cφ(u2)={5,6,7,8,10}.现用11给uv着色可得G的一个12-邻点可区别边着色,矛盾.若cφ(u2)={q,5,6,7,8},由于|L(uu2)|≥3,所以存在s∈L(uu2)\cφ(u1).现用s给uu2重新着色,用12给uv着色可得G的一个12-邻点可区别边着色,矛盾.假设|Av∩{9,10,11,12}|=2. 因而|Au∩{9,10,11,12}|=2. 不妨设cφ(v1)={1,2,3,4,9},cφ(v2)={1,2,3,4,10},cφ(u1)={5,6,7,8,11}和c(u2)={5,6,7,8,12}. 由于|L(uu1)|≥3,所以存在q∈L(uu1)\cφ(u2).现用q给uu1重新着色,用12给uv着色可得G的一个12-邻点可区别边着色,矛盾.情形3.3.2 假设|cφ(u)∩cφ(v)|=1.不妨设φ(uu1)=1和φ(uuj)=j+3,其中j=2,3,4.若存在p∈C\{cφ(v)∪cφ(u)},用p 给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,在φ下,{{p}∪cφ(v)}∈Ω(v),或{{p}∪cφ(u)}∈Ω(u).显然,C\{cφ(v)∪cφ(u)}={8,9,10,11,12}.假设|Av∩{8,9,10,11,12}|=4.因而|Au∩{8,9,10,11,12}|≥1.不妨设cφ(v1)={1,2,3,4,8},cφ(v2)={1,2,3,4,9},cφ(v3)={1,2,3,4,10},cφ(v4)={1,2,3,4,11}和cφ(u1)={1,5,6,7,12}.若存在q∈{5,6,7,12},使得{q,1,3,4,9}Ωv(v2),那么先用q给vv2重新着色.进一步,若用2给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,cφ(u2)={1,2,5,6,7}.现用10给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,在φ下,Ωv(v2)={{1,3,4,5,9},{1,3,4,6,9},{1,3,4,7,9},{1,3,4,9,12}}.先用10给vv2重新着色.进一步,若用8给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,cφ(u2)={1,5,6,7,8}.现用11给uv着色可得G的一个12-邻点可区别边着色,矛盾.假设|Av∩{8,9,10,11,12}|=3.因而|Au∩{8,9,10,11,12}|=2.不妨设cφ(v1)={1,2,3,4,8},cφ(v2)={1,2,3,4,9},cφ(v3)={1,2,3,4,10},cφ(u1)={1,5,6,7,11}和cφ(u2)={1,5,6,7,12}.由于|L(uu2)|≥3,所以存在q∈L(uu2)\cφ(u1).现用q给uu2重新着色,用11给uv着色可得G的一个12-邻点可区别边着色,矛盾.情形3.3.3 假设|cφ(u)∩cφ(v)|=2.不妨设φ(uu1)=1,φ(uu2)=2,φ(uu3)=5 和φ(uu4)=6. 若存在p∈C\{cφ(v)∪cφ(u)},用p给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,在φ下,{{p}∪cφ(v)}∈Ω(v)或{{p}∪cφ(u)}∈Ω(u).显然,C\{cφ(v)∪cφ(u)}={7,8,9,10,11,12}.不妨设cφ(v1)={1,2,3,4,7},cφ(v2)={1,2,3,4,8},cφ(v3)={1,2,3,4,9},cφ(v4)={1,2,3,4,10},c φ(u1)={1,2,5,6,11}和cφ(u2)={1,2,5,6,12}. 由于|L(uu1)|≥3,所以存在q∈L(uu1)\cφ(u2).现用q给uu1重新着色,用12给uv着色可得G的一个12-邻点可区别边着色,矛盾.情形3.3.4 假设|cφ(u)∩cφ(v)|=3.显然,存在p∈C\{cφ(v)∪cφ(u)},用p给uv着色可得G的一个12-邻点可区别边着色,矛盾.情形3.3.5 假设|cφ(u)∩cφ(v)|=4.与情形3.2.4类似,矛盾.情形3.4 假设d(uj)=5,其中j=1,2,3,且d(u4)=6.情形3.4.1 假设|cφ(u)∩cφ(v)|=0.不妨设φ(uuj)=j+4,j=1,2,3,4.若存在p∈C\{cφ(v)∪cφ(u)},用p给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,在φ下,{{p}∪cφ(v)}∈Ω(v)或{{p}∪cφ(u)}∈Ω(u).显然,C\{cφ(v)∪cφ(u)}={9,10,11,12}.假设|Av∩{9,10,11,12}|=4. 不妨设cφ(v1)={1,2,3,4,9},cφ(v2)={1,2,3,4,10},cφ(v3)={1,2,3,4,11}和cφ(v4)={1,2,3,4,12}.若存在q∈{5,6,7,8},使得{q,2,3,4,9}Ωv(v1),那么先用q给vv1重新着色.进一步,若用1给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,cφ(u1)={1,5,6,7,8}或cφ(u2)={1,5,6,7,8}或cφ(u3)={1,5,6,7,8}.不妨设cφ(u1)={1,5,6,7,8}.若用10给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,cφ(u2)={5,6,7,8,10}或cφ(u3)={5,6,7,8,10}.不妨设cφ(u2)={5,6,7,8,10}.若用11给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,cφ(u3)={5,6,7,8,11}.现用12给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,在φ下,Ωv(v1)={{2,3,4,5,9},{2,3,4,6,9},{2,3,4,7,9},{2,3,4,8,9}}.类似的,Ωv(v2)={{1,3,4,5,10},{1,3,4,6,10},{1,3,4,7,10},{1,3,4,8,10}},Ωv(v3)={{1,2,4,5,1 1},{1,2,4,6,11},{1,2,4,7,11},{1,2,4,8,11}}和Ωv(v4)={{1,2,3,5,12},{1,2,3,6,12},{1,2,3,7,12},{1,2,3,8,12}}.先用10,11,12和9分别给vv1,vv2,vv3和vv4重新着色.进一步,若用1给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,cφ(u1)={1,5,6,7,8}或cφ(u2)={1,5,6,7,8}或cφ(u3)={1,5,6,7,8}. 不妨设cφ(u1)={1,5,6,7,8}.若用2给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,cφ(u2)={2,5,6,7,8}或cφ(u3)={2,5,6,7,8}. 不妨设cφ(u2)={2,5,6,7,8}. 若用 3给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,cφ(u3)={3,5,6,7,8}.现用4给uv着色可得G的一个12-邻点可区别边着色,矛盾.假设|Av∩{9,10,11,12}|=3. 因而|Au∩{9,10,11,12}|≥1. 不妨设cφ(v1)={1,2,3,4,9},cφ(v2)={1,2,3,4,10},cφ(v3)={1,2,3,4,11}和cφ(u1)={5,6,7,8,12}.由于|L(uu1)|≥3,所以存在q∈L(uu1).若用q给uu1重新着色,用5给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,cφ(u2)={q,5,6,7,8}或cφ(u3)={q,5,6,7,8}或cφ(v4)={1,2,3,4,5}. 若cφ(v4)={1,2,3,4,5},显然,存在r∈{5,6,7,8,12},使得{r,2,3,4,9}Ωv(v1),那么先用r给vv1重新着色.进一步,若用10给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,cφ(u2)={5,6,7,8,10}或cφ(u3)={5,6,7,8,10}.不妨设cφ(u2)={5,6,7,8,10}.若用11给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,cφ(u3)={5,6,7,8,11}.显然存在s∈{6,7}\{r},不妨设s=7.由于|L(uu3)|≥3,所以存在t∈L(uu3)\{cφ(u1)∪cφ(u2)}.现用t给uu3重新着色,用7给uv着色可得G的一个12-邻点可区别边着色,矛盾.若cφ(u2)={q,5,6,7,8}或cφ(u3)={q,5,6,7,8},不妨设cφ(u2)={q,5,6,7,8}.由于|L(uu2)|≥3,所以存在r∈L(uu2)\cφ(u1).若用r给uu2重新着色,用12给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,cφ(u3)={r,5,7,8,12}.由于|L(uu3)|≥2,所以存在s∈L(uu3).显然,scφ(u1),6cφ(u3)和12cφ(u2).因而用s给uu3重新着色,用12给uv着色可得G的一个12-邻点可区别边着色,矛盾.假设|Av∩{9,10,11,12}|=2.因而|Au∩{9,10,11,12}|≥2.不妨设cφ(v1)={1,2,3,4,9},cφ(v2)={1,2,3,4,10},cφ(u1)={5,6,7,8,11}和cφ(u2)={5,6,7,8,12}. 由于|L(uu1)|≥3,所以存在q∈L(uu1)\cφ(u2).若用q给uu1重新着色,用12给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,cφ(u3)={q,6,7,8,12}.由于|L(uu2)|≥3,所以存在r∈L(uu2)\{cφ(u1)∪cφ(u3)}.现用r给uu2重新着色,用11给uv着色可得G的一个12-邻点可区别边着色,矛盾. 假设|Av∩{9,10,11,12}|=1.因而|Au∩{9,10,11,12}|=3.不妨设cφ(v1)={1,2,3,4,9},cφ(u1)={5,6,7,8,10},cφ(u2)={5,6,7,8,11}和cφ(u3)={5,6,7,8,12}. 由于|L(uu1)|≥3,所以存在q∈L(uu1)\{cφ(u2)∪cφ(u3)}.现用q给uu1重新着色,用11给uv着色可得G的一个12-邻点可区别边着色,矛盾.情形3.4.2 假设|cφ(u)∩cφ(v)|=1.不妨设φ(uu1)=1,φ(uuj)=j+3,j=2,3,4.若存在p∈C\{cφ(v)∪cφ(u)},用p给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,在φ下,{{p}∪cφ(v)}∈Ω(v)或{{p}∪cφ(u)}∈Ω(u).显然,C\{cφ(v)∪cφ(u)}={8,9,10,11,12}.假设|Av∩{8,9,10,11,12}|=4.因而|Au∩{8,9,10,11,12}|≥1.不妨设cφ(v1)={1,2,3,4,8},cφ(v2)={1,2,3,4,9},cφ(v3)={1,2,3,4,10},cφ(v4)={1,2,3,4,11}和cφ(u1)={1,5,6,7,12}.若存在q∈{5,6,7,12},使得{q,1,3,4,9}Ωv(v2),那么先用q 给vv2重新着色.进一步,若用2给uv着色可得G的一个12-邻点可区别边着色,矛盾. 否则,cφ(u2)={1,2,5,6,7}或cφ(u3)={1,2,5,6,7}. 不妨设cφ(u2)={1,2,5,6,7}.若用8给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,cφ(u3)={1,5,6,7,8}.现用10给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,在φ下,Ωv(v2)={{1,3,4,5,9},{1,3,4,6,9},{1,3,4,7,9},{1,3,4,9,12}}.类似的,Ωv(v3)={{1,2,4,5,10},{1,2,4,6,10},{1,2,4,7,10},{1,2,4,10,12}}和Ωv(v4)={{1,2,3,5,11},{1,2,3,6,11},{1,2,3,7,11},{1,2,3,11,12}}.先用10,11和9分别给vv2,vv3和vv4重新着色.进一步,若用2给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,cφ(u2)={1,2,5,6,7}或cφ(u3)={1,2,5,6,7}. 不妨设cφ(u2)={1,2,5,6,7}.若用 3给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,cφ(u3)={1,3,5,6,7}.现用4给uv着色可得G的一个12-邻点可区别边着色,矛盾.假设|Av∩{8,9,10,11,12}|=3.因而|Au∩{8,9,10,11,12}|≥2.不妨设cφ(v1)={1,2,3,4,8},cφ(v2)={1,2,3,4,9},cφ(v3)={1,2,3,4,10},cφ(u1)={1,5,6,7,11}和cφ(u2)={1,5,6,7,12}.由于|L(uu1)|≥3,所以存在q∈L(uu1)\cφ(u2).若用q给uu1重新着色,用12给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,cφ(u3)={q,5,6,7,12}.由于|L(uu2)|≥3,所以存在r∈L(uu2)\{cφ(u1)∪cφ(u3)}.现用r给uu2重新着色,用11给uv着色可得G的一个12-邻点可区别边着色,矛盾. 假设|Av∩{8,9,10,11,12}|=2.因而|Au∩{8,9,10,11,12}|=3.不妨设cφ(v1)={1,2,3,4,8},cφ(v2)={1,2,3,4,9},cφ(u1)={1,5,6,7,10},cφ(u2)={1,5,6,7,11}和cφ(u3)={1,5,6,7,12}. 由于|L(uu2)|≥3,所以存在q∈L(uu2)\{cφ(u1)∪cφ(u3)}. 现用q给uu2重新着色,用12给uv着色可得G的一个12-邻点可区别边着色,矛盾.情形3.4.3 假设|cφ(u)∩cφ(v)|=2.不妨设φ(uu1)=1,φ(uu2)=2,φ(uu3)=5 和φ(uu4)=6. 若存在p∈C\{cφ(v)∪cφ(u)},用p给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,在φ下,{{p}∪cφ(v)}∈Ω(v)或{{p}∪cφ(u)}∈Ω(u).显然,C\{cφ(v)∪cφ(u)}={7,8,9,10,11,12}.假设|Av∩{7,8,9,10,11,12}|=4.因而|Au∩{7,8,9,10,11,12}|≥2.不妨设cφ(v1)={1,2,3,4,7},cφ(v2)={1,2,3,4,8},cφ(v3)={1,2,3,4,9},cφ(v4)={1,2,3,4,10},c φ(u1)={1,2,5,6,11}和cφ(u2)={1,2,5,6,12}.由于|L(uu1)|≥3,所以存在q∈L(uu1)\cφ(u2).若用q给uu1重新着色,用12给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,cφ(u3)={q,2,5,6,12}.由于|L(uu2)|≥3,所以存在r∈L(uu2)\{cφ(u1)∪cφ(u3)}.现用r给uu2重新着色,用11给uv着色可得G的一个12-邻点可区别边着色,矛盾.假设|Av∩{7,8,9,10,11,12}|=3.因而|Au∩{7,8,9,10,11,12}|=3.不妨设cφ(v1)={1,2,3,4,7},cφ(v2)={1,2,3,4,8},cφ(v3)={1,2,3,4,9},cφ(u1)={1,2,5,6,10},c φ(u2)={1,2,5,6,11}和cφ(u3)={1,2,5,6,12}.由于|L(uu3)|≥3,所以存在q∈L(uu3)\{cφ(u1)∪cφ(u2)}.现用q给uu3重新着色,用10给uv着色可得G的一个12-邻点可区别边着色,矛盾.情形3.4.4 假设|cφ(u)∩cφ(v)|=3.不妨设φ(uuj)=j,其中j=1,2,3.设φ(uu4)=5.若存在p∈C\{cφ(v)∪cφ(u)},用p给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,在φ下,{{p}∪cφ(v)}∈Ω(v)或{{p}∪cφ(u)}∈Ω(u). 显然,C\{cφ(v)∪cφ(u)}={6,7,8,9,10,11,12}. 不妨设cφ(v1)={1,2,3,4,6},cφ(v2)={1,2,3,4,7},cφ(v3)={1,2,3,4,8},cφ(v4)={1,2,3,4,9},cφ( u1)={1,2,3,5,10},cφ(u2)={1,2,3,5,11}和cφ(u3)={1,2,3,5,12}.由于|L(uu1)|≥3,所以存在q∈L(uu1)\{cφ(u2)∪cφ(u3)}.现用q给uu1重新着色,用11给uv着色可得G的一个12邻点可区别边着色,矛盾.情形3.4.5 假设|cφ(u)∩cφ(v)|=4.与情形3.2.4类似,矛盾.情形3.5 假设d(uj)=5,其中j=1,2,3,4.由于G是最大度为6的连通图,所以在G中存在一个6-顶点w,和一条最短路p=w0,w1,···,wt,其中w0=u,wt=w.设ws是这条路上的第一个6-顶点.根据情形1,2和3.1–3.4可知d(wk)=5且s≥3,其中k=0,1,···,s−1.因此找到了一个5-顶点ws−1和一个6-顶点ws相邻.令H=G−ws−2ws−1.正如前面已讨论,矛盾.因此这个定理成立.推论2.1 设G是一个最大度为6的图,则.证由引理1.1和定理2.1可得.参考文献【相关文献】[1]Zhang Zhongfu,Liu Linzhong,Wang Jianfang.Adjacent strong edge coloring ofgraphs[J].Appl.Math.Lett.,2002,15(5):623–626.[2]Hatami H.∆+300 is a bound on the adjacent vertex distinguishing edge chromatic number[J]bin.Theory Ser.B.,2006,95(2):246–256.[3]Akbari S,Bidkhori H,Nosrati N.r-Strong edge colorings ofgraphs[J].Disc.Math.,2006,306(23):3005–3010.[4]Zhang Lianzhu,Wang Weifan,Lih K W.An improved upper bound on the adjacent vertexdistinguishing chromatic index of a graph[J].Disc.Appl.Math.,2014,162(C):348–354.[5]Balister P N,Gyri 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]b.Optim.,2013,26(1):152–160.[7]Wang Yiqiao,Wang Weifan,Huo Jingjing.Some bounds on the neighbor-distinguishing index of graphs[J].Disc.Math.,2015,338(11):2006–2013.。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
Ａｂｓ ｒ ｃ ｔ ａ ｔ： Ｉ ｗａｓｐｒ ｖｅ ｈａ ｖｅ ｙ ｇ ａ ｔ ｔ ｏ ｄ ｔ ｔｅ ｒ ｒ ｐｈ ｗｉｈ ｖｅ ｉｅ ｎｄ ｗ ｉｈ ｍ ａ ｍ ｕｍ ｇ ｅ Ａ ≥ ２ ｈａ ｅ ｔ ｘ ｄ ｓｉｇｕｉｈｎｇ ｔ ｒ ｃ ｓ ａ ｔ ｘｉ ｄｅ ｒ ｅ ｓ ａ ｖ ｒｅ ｉｔｎ ｓｉ
Ａ Ｎ ｉ ｇ ｑ ａ ｇ， Ｍ ＥＮ Ｇ ｉ ｎ — ｏ Ｍ ｎ — ｉｎ Ｘ ａ ｇｂ
（ ｏｌ ｅ ｆ ｃ ｎ ｅＴａｊ ｎｖ ｒｉ ｆ ｃｅｃ ＆ Ｔｃ ｎ ｌｇ ，ｉｎｉ ０ ４ ７Ｃ ｉａ Ｃ ｌ ｇ ｉ ｃ ，ｉｎｉ Ｕ ｉｅｓｙｏ ｉｎｅ ｅ ｏＳ ｅ ｎ ｔ Ｓ ｅｈ ｏｏ ｙＴａｊ ３ ０ ５ ，ｈｎ ） ｎ
受 文 献 ［ ］ ６ ７ 的启 发 ， 鉴 文 献 ［】 概 率 方 法 改 进 图 借 ８用
的星色 数上 界 的经 验 ， 针对 点表示 Ｇ的 ｋ度顶 点 个 ｄｃ图 ／（ ） ７
ｌ， 、 ｒ ，
别 全染 色 ， 试应 用 概 率 方 法 ， 别 得 到 了其 色数 的 尝 分
收稿 日期 ：２ １ － ７ ２ ；修 回 日期 ：２ １一 — ６ ０ ０ ０— ０ ００ ｌ ２ １
基 金项 目 ：天 津 科 技 大 学 科 学 研 究 基 金 资 助 项 目 （０ ９ ２ ２ ２００２） 作者 简 介 ：安 明 强 （ ９２ ），男 ，甘 肃 灭 水 人 ，讲 师 ，ａｍｑ ｕ ｔｄ ． １８ 一 ｎ ＠ｔｓｅｕｃ ． ｎ
本 文 所 考 虑 的 均 为连 通 的 、 限 的 、 向的 简 有 兀
ｋ是 正整 数 ， 厂是 从 Ｖ Ｇ ＵＥ Ｇ 到 ｛ ２…，｝ 若 （ ） （ ） １ ， ｋ 的一 ，
单 冈． 文献 ［— ］ 罔 的点 可 区别 边 染 色 （ １ ３对 或称 强 边 染 色） 问题 进 行 讨 论 ， 到 了 许多 重 要 的结 果 ． 忠 辅 得 张 等 Ｉ 研究 图 的点 可 区 别 全染 色 ， 到 了某 些 特 殊 图 ４ Ｉ 得 的具 体 的点 可 区别 全 色数 ． 年来 ， 概 率 方 法 来研 近 用
，
） ．
，
事 １ ∑ ｒｉ≤ ｒ Ｊ 实１ 一 ＰＡＩＰ ｎ ． Ｊ （） ＼ Ｊ
ｉ１ ＝ ＼ ｉ１ ＝ ／
因为 ， （ ） （ ＝
）÷ 通过 ＝ ， 期望的 线性性
＝
／ ‘ ‘
Ｍａ ｋ ｖ 不 等 式 Ｉ 对 任 意 的正 随 机 变量 ， ｒｏ ９ ］ 有
Ｖｕ ∈ （ “≠ｖ Ｃ（ ） ， Ｇ）（ ）， “ ≠Ｃ（）， ｖ
（） Ｉ 对每两 条相邻 的边 Ｐ ｇ 令 ，，
如 ’
＝
一样
其中 Ｃｕ＝厂 ｝ ｛（ ）Ｅ ６， Ｅ ６｝ 贝 厂 （ ｛（ Ｕｆｕ ｌ （）Ｖ （）， ） ） ｖｖ Ｕ
称 为 Ｇ的一 个 ｋ 点 可 区别 全染 色 ， 一 简记 为 ｋ Ｖ Ｔ — Ｄ Ｃ．
ｌ ｌ 、 ／ ｔ
』 果和 ｃ） （ ｝ ｌ ”满足 （＝Ｖ ，如 “ｃ）
０ ， 否则
ｍ｛ ＋≥（ ｄＡ则 ｉ １ Ｇ ≤≤｝ 有 ｎ ） ｆ ｊ ， 《 ’
猜 想 ２５ 对 简单 图 Ｇ， （） ， （） 【 】 Ｉ ＧＩ 有 Ｇ ≤ ≥２
（ ≤ ｋ （ ＋１ Ｇ） ｒＧ） ．
ｍｅｈ ｄ ｔ ｔ ｏ ．Ｉ ｗａ ａｓ ｒ ｖ ｄ ｔ ａ ｖ ｒ ｒ ｐ ｗｉ ， ≥ ３ ｖ ｒｉｅ ａ ｄ ｓ ｌｏ ｐ ｏ ｅ ｈ ｔ ｅ ｅ ｇ ａ ｈ ｙ ｔ ｚ ｈ ｅｔｃ ｓ ｎ ｗｉ ｍａ ｉ ｍ ｄ ｇ ｅ Ａ ≥ １ ｈ ｓ ｅ ｔ ｘ ｔ ｈ ｘ ｍｕ ｅ ｒｅ ａ ａ ｖ ｒ ｅ
定义 ２ Ｊ 设 Ｇ是 阶数至少 是 ２ 的简单连通 图 ， ｌ ４ 后是 正 整 数 ， － 若 厂是从 ＶＧ） （ 到 ｛ ２…，｝ （ ＵＥ Ｇ） １ ， ｋ 的一 ， 个映射 ， 使得
Ｖ ｖ （ ）厂“ ≠＿ ｖ ｆ “ ≠． “） 厂Ｖ ； ｕ ｅＥ Ｇ ， （） 厂 ）， （） 厂 １≠ｈ ） ＿ （ （， （ Ｖ ｖＵ Ｅ （ ） ≠Ｗ ， （ｖ≠．（ ） ｕ ，ｗ Ｇ （ ｖ ） ｆ ｕ） ｆｕ ； ｗ
已 成 为 目前 困 际 上 比 较 热 门 的研 究 领 域 之 一 ．
Ｈａａ ［用 概 率 方 法 研 究 并 确 定 了 图 的邻 点 可 区别 ｔｍｉ ６ 边 色数 的 卜 为 △＋ ０ 刘信 生 等 用 概 率方 法 研 究 界 ３ ０． ｊ 并 确 定 了邻 点 可 区别 的 无 圈 边 色 数 的上 界 为 ３ Ａ． ２
上 界．
数． Ｊ ）ｍ ｛， 『 Ｇ，≤ｋ ｝ （） 令／Ｇ＝ ｉｌ：≥ ） ≤△， Ｇ称为 （ ｎ［ （ ｆ ｌ ｃ
图 Ｇ的组合 度 ， 然 、 ） （ ） 显 Ｇ ≥Ｈ Ｇ ． 猜 想 ｊ 设 Ｇ是 ｖｅ 图 ， （ ） 图 Ｇ的组 合 ｄｃ Ｇ 为
定义 １１ 设 Ｇ是 阶数 至少 是 ２的简 单连 通 图 ， 【 Ｊ
Ｔｗｏ Ｕｐｐｅ ｕｎ ｏ ｈｅＶｅ ｔｘ— ｓｉ ｕｉｈｉ — ｒＢｏ ｄｓｆ ｒｔ ｒ ｅ Ｄｉｔｎｇ ｓ ｎｇ Ｅｄｇ ｅＣｈｒ ｍ ａ ｉ ｏ ｔｃ Ｎｕｍ ｂｅ ｓａ ｒｅ Ｄｉｔｎｇ ｓ ｉ — ｔ ｌＣｈｒ ｍ ａ ｉ ｕ ｂｅ ｓ ｒ ｎｄ Ｖｅ ｔｘ— ｓｉ ｕｉｈ ｎｇ Ｔｏ ａ ｏ ｔｃＮ ｍ ｒ
该 引 理 多 用 于 是 正 整 数 值 且 Ｅ ） ， 有 （ ＜１ 则
尸， ＝０＞０ ． （ ） ．
不 等 式 ：Ｐ （ ｒＸ￣Ｏ ≤Ｅ Ｘ）， 以 只 需 证 Ｅ Ｘ） ） （ 所 （ ＋
（ ） 即可 ． ｙ＜１
由概 率论知识 可 知
厂 、 厂 ｔ ／ 、
首先 ， 计算
区 别 的 边 色数 ， ≤ ｎ （ 一１ ， ｎ≥ ３， （ Ｇ） Ａ ｎ ） 当 △≥ １ ， 点 可 区 别 的 全 色数 ｚ Ｇ） ２ Ａ ｎ ） 时 其 ， ≤ ｎ （ 一１ ． （ 关 键 词 ：边 染 色 ； 令染 色 ；点 可 Ｉ 边 色 数 ；点 可 区别 全 色数 ；慨 率 方 法 别 中 图分 类 号 ：Ｏ１７５ ５． 文 献 标 志 码 ：Ａ 文章 编 号 ：ｌ ７—５ ０ ２ １） １０ ７ —４ ６ ２６ １ （０ １０ —０ ５０
｛ ＝０ ， ，＝０ 且 ＝｛ ｝ Ａ ＝｛ ， ｝， ＞０ ＝ ｛＞０ ） ）， ｙ ｝， 即只需 证 尸 （ ｒ ＞０ ＋Ｐ （＞Ｏ＜Ｉ ） ｒＹ ） 即可 ． 又根 据 Ｍａｋ ｖ ｒｏ
引理 １］ （ 一矩量原理 ） 【 ９ 第 如果 Ｅ Ｘ） ， （ ≤ｔ 则
（ ≤ ，＞０ ） ．
・
７ ・ ６
天津科 技大 学学报 第 ２ 卷 第 １ ６ 期 （ 正常 ） 边染 色 ， 须使 以下两 点成立 ： 必 （） 常边染 色 ， １正
（） 意两个点 点可 区别 ． ２任 为此 ， 义如 下指标 变量 ： 定
度 ， ＸＡＧ ： Ｇ ， 则 ｖ ） （ ） 或者 （ ） （ ＋１ ＇ Ｇ ＝ Ｇ） ．
并令 ＝ ∑ ，， 注意到 即是不满足正常
边染 色 的相邻边 对 的数量 ． （ ） 在两个 点 “ ｖ 令 Ｉ存 Ｉ ，，
ｙ ：
称ｍｎ ｌ ｋ Ｖ Ｔ ｝ ｉｋ ￣ — Ｄ Ｃ 为Ｇ的点可区别全色数， ｛ａ 记
为 （ ． Ｇ）
令 ｎ（ ） 示 Ｇ 的 ｄ度 顶 点 的 个 数 ， ｋ（ ） ａＧ 表 令 ＴＧ ＝
究 图 的染 色 问题 ， 到 了 国 内外学 术 界 的普 遍 关 注 ， 受
个 映 射 ， 得 Ｖ ｖ，Ａ Ｅ （ （≠ｗ ，厂“） （ｗ 使 ｕ Ｉ Ｇ） Ｗ ） ｌ ｖ≠ｆ ｕ ）； （
Ｖ ｖ （ ） ｖ ， （） Ｃ ｖ ， ． ∈ＶＧ （ ≠ ） Ｃｕ ≠ （ 其中 Ｃｕ＝ 厂 ｖ ） （ ｔ（ ） ） Ｉ
ｅ ｇ ｏｏ ｉｇ ｗｉ ｔｍｏ ｔ Ａ（ ｄ ｅｃ ｌｒ ｔ ａ ｓ ｎ ｎ一１ ｃ ｌｒ ｙ ｕ ｉｇ ｔｅ ｆ ｓ ｍｅ ｔｐ ｉｃｐｅａ ｄ Ｍａｋ ｖＳｉｅ ｕ ｌｙ ｏ ｒ ｂ ｂｌ ｔｃ ｎ ｈ ） ｏｏｓｂ ｓｎ ｈ ｉ ｔｍｏ ｎ ｒｎ ｉｌ ｎ ｒ ｏ ’ ｎ ｑ ａｉ ｆｐ ｏ ａ ｉｓｉ ｒ ｔ ｉ
１ （ ） Ｖ （ ） ， ｆ称 为 Ｇ的一 个 ｋ一 可 区别 ， Ｇ， ＠ Ｇ｝ 则 ∈ Ｈ 点
边染色 ， 简记为 ｋ Ｖ Ｅ 称 ｍｎｋＧ — Ｄ Ｃ． ｉ｛ｌ存在 Ｖ Ｅ ｝ 一 Ｄ Ｃ
为 Ｇ 的 点 可 区别 边 色 数 （ 称 为 强 边 色 数 ） 记 为 或 ， （ ）（ Ｇ 或 （ ） ． Ｇ） 显 然 ， 个 图 Ｇ具有 点 可 区别 的边染 色 当且仅 当 一 图 Ｇ是没 有 孤 立边 ， 最 多 有一 个 孤立 点 的 图． 样 且 这 的 图称 为 ｖ ｅ 图． ｄｃ
ｄ ｓｉｇ ｉ ｉｇｔｔｌ ｏｏ ｉｇｗｉ ｔ ｓ ２ Ａ（ ｉｔ ｕｓ ｎ ａ ｌｒ ｔ ａ ｔ ｎ ｎ一１ ｃ ｌｒ． ｎ ｈ ｏ ｃ ｎ ｈ ｍｏ ） ｏｏ ｓ
Ｋｅ ｙｗｏｒ ｄｓ： ｅ ｅ ｏｌ ｉ ｄｇ ｃ ｏｒｎｇ； ｔ ｔ ｌ ｏｌ ｉ ｏ ａ ｃ ｏｒｎｇ； ｖｅ ｅ ｄ ｓｉ ｕｉｈ ｎ ｅ ｇｅ ｈ ｏｍ ａｉ ｎ ｔ ｒ ｘ ｉｔｎｇ ｓ ｉ ｇ ｄ ｃ ｒ ｔｃ ｕｍｂｅ ｒ； ｖ ｒｅ ｄｉｔｎ ｉｈｉ ｔ ｔ ｌ ｅ ｘ ｔ ｓｉ ｇｕ ｓ ｎｇ ｏ ａ ｃ ｏ ａ ｉ ｕｍ ｂ ｒ ｐｒ ｂａ ｌｓｉ ｅｈｏ ｈｒ ｍ ｔｃｎ ｅ； ｏ ｂｉｉｔｃｍ ｔ ｄ
２ ｄ（ ｎ ｎ—ｎ ２
１
确 定一 般 图的点可 区别 边 （ ） 数 的上 界 ， 全 色 对于 特殊 图的点 可 区别 边 （ 色 数 的确 定 ， 全） 具有 非常 重要
并令Ｙ ∑ ＝
， 注意到Ｙ即是不满足任意两
点点可 区别 的点 对 的数量 ． 现 只要证 （ ＝０ 且Ｙ：０＞０， 根据事 实 １ ） 又 可得 Ｐ （ ＝Ｏ ， ０ ≥１ ［ Ｊ Ｊ 且）＝ ） 一 Ｐ （ ） 一， ｏ ＞０（ ４ ＝ ＞０＋ （＝ ） 】＞ 】 令
Ａ Ｎ ｉ ｇ ｑ ａ ｇ， Ｍ ＥＮ Ｇ ｉ ｎ — ｏ Ｍ ｎ — ｉｎ Ｘ ａ ｇｂ
（ ｏｌ ｅ ｆ ｃ ｎ ｅＴａｊ ｎｖ ｒｉ ｆ ｃｅｃ ＆ Ｔｃ ｎ ｌｇ ，ｉｎｉ ０ ４ ７Ｃ ｉａ Ｃ ｌ ｇ ｉ ｃ ，ｉｎｉ Ｕ ｉｅｓｙｏ ｉｎｅ ｅ ｏＳ ｅ ｎ ｔ Ｓ ｅｈ ｏｏ ｙＴａｊ ３ ０ ５ ，ｈｎ ） ｎ
受 文 献 ［ ］ ６ ７ 的启 发 ， 鉴 文 献 ［】 概 率 方 法 改 进 图 借 ８用
的星色 数上 界 的经 验 ， 针对 点表示 Ｇ的 ｋ度顶 点 个 ｄｃ图 ／（ ） ７
ｌ， 、 ｒ ，
别 全染 色 ， 试应 用 概 率 方 法 ， 别 得 到 了其 色数 的 尝 分
收稿 日期 ：２ １ － ７ ２ ；修 回 日期 ：２ １一 — ６ ０ ０ ０— ０ ００ ｌ ２ １
基 金项 目 ：天 津 科 技 大 学 科 学 研 究 基 金 资 助 项 目 （０ ９ ２ ２ ２００２） 作者 简 介 ：安 明 强 （ ９２ ），男 ，甘 肃 灭 水 人 ，讲 师 ，ａｍｑ ｕ ｔｄ ． １８ 一 ｎ ＠ｔｓｅｕｃ ． ｎ
本 文 所 考 虑 的 均 为连 通 的 、 限 的 、 向的 简 有 兀
ｋ是 正整 数 ， 厂是 从 Ｖ Ｇ ＵＥ Ｇ 到 ｛ ２…，｝ 若 （ ） （ ） １ ， ｋ 的一 ，
单 冈． 文献 ［— ］ 罔 的点 可 区别 边 染 色 （ １ ３对 或称 强 边 染 色） 问题 进 行 讨 论 ， 到 了 许多 重 要 的结 果 ． 忠 辅 得 张 等 Ｉ 研究 图 的点 可 区 别 全染 色 ， 到 了某 些 特 殊 图 ４ Ｉ 得 的具 体 的点 可 区别 全 色数 ． 年来 ， 概 率 方 法 来研 近 用
，
） ．
，
事 １ ∑ ｒｉ≤ ｒ Ｊ 实１ 一 ＰＡＩＰ ｎ ． Ｊ （） ＼ Ｊ
ｉ１ ＝ ＼ ｉ１ ＝ ／
因为 ， （ ） （ ＝
）÷ 通过 ＝ ， 期望的 线性性
＝
／ ‘ ‘
Ｍａ ｋ ｖ 不 等 式 Ｉ 对 任 意 的正 随 机 变量 ， ｒｏ ９ ］ 有
Ｖｕ ∈ （ “≠ｖ Ｃ（ ） ， Ｇ）（ ）， “ ≠Ｃ（）， ｖ
（） Ｉ 对每两 条相邻 的边 Ｐ ｇ 令 ，，
如 ’
＝
一样
其中 Ｃｕ＝厂 ｝ ｛（ ）Ｅ ６， Ｅ ６｝ 贝 厂 （ ｛（ Ｕｆｕ ｌ （）Ｖ （）， ） ） ｖｖ Ｕ
称 为 Ｇ的一 个 ｋ 点 可 区别 全染 色 ， 一 简记 为 ｋ Ｖ Ｔ — Ｄ Ｃ．
ｌ ｌ 、 ／ ｔ
』 果和 ｃ） （ ｝ ｌ ”满足 （＝Ｖ ，如 “ｃ）
０ ， 否则
ｍ｛ ＋≥（ ｄＡ则 ｉ １ Ｇ ≤≤｝ 有 ｎ ） ｆ ｊ ， 《 ’
猜 想 ２５ 对 简单 图 Ｇ， （） ， （） 【 】 Ｉ ＧＩ 有 Ｇ ≤ ≥２
（ ≤ ｋ （ ＋１ Ｇ） ｒＧ） ．
ｍｅｈ ｄ ｔ ｔ ｏ ．Ｉ ｗａ ａｓ ｒ ｖ ｄ ｔ ａ ｖ ｒ ｒ ｐ ｗｉ ， ≥ ３ ｖ ｒｉｅ ａ ｄ ｓ ｌｏ ｐ ｏ ｅ ｈ ｔ ｅ ｅ ｇ ａ ｈ ｙ ｔ ｚ ｈ ｅｔｃ ｓ ｎ ｗｉ ｍａ ｉ ｍ ｄ ｇ ｅ Ａ ≥ １ ｈ ｓ ｅ ｔ ｘ ｔ ｈ ｘ ｍｕ ｅ ｒｅ ａ ａ ｖ ｒ ｅ
定义 ２ Ｊ 设 Ｇ是 阶数至少 是 ２ 的简单连通 图 ， ｌ ４ 后是 正 整 数 ， － 若 厂是从 ＶＧ） （ 到 ｛ ２…，｝ （ ＵＥ Ｇ） １ ， ｋ 的一 ， 个映射 ， 使得
Ｖ ｖ （ ）厂“ ≠＿ ｖ ｆ “ ≠． “） 厂Ｖ ； ｕ ｅＥ Ｇ ， （） 厂 ）， （） 厂 １≠ｈ ） ＿ （ （， （ Ｖ ｖＵ Ｅ （ ） ≠Ｗ ， （ｖ≠．（ ） ｕ ，ｗ Ｇ （ ｖ ） ｆ ｕ） ｆｕ ； ｗ
已 成 为 目前 困 际 上 比 较 热 门 的研 究 领 域 之 一 ．
Ｈａａ ［用 概 率 方 法 研 究 并 确 定 了 图 的邻 点 可 区别 ｔｍｉ ６ 边 色数 的 卜 为 △＋ ０ 刘信 生 等 用 概 率方 法 研 究 界 ３ ０． ｊ 并 确 定 了邻 点 可 区别 的 无 圈 边 色 数 的上 界 为 ３ Ａ． ２
上 界．
数． Ｊ ）ｍ ｛， 『 Ｇ，≤ｋ ｝ （） 令／Ｇ＝ ｉｌ：≥ ） ≤△， Ｇ称为 （ ｎ［ （ ｆ ｌ ｃ
图 Ｇ的组合 度 ， 然 、 ） （ ） 显 Ｇ ≥Ｈ Ｇ ． 猜 想 ｊ 设 Ｇ是 ｖｅ 图 ， （ ） 图 Ｇ的组 合 ｄｃ Ｇ 为
定义 １１ 设 Ｇ是 阶数 至少 是 ２的简 单连 通 图 ， 【 Ｊ
Ｔｗｏ Ｕｐｐｅ ｕｎ ｏ ｈｅＶｅ ｔｘ— ｓｉ ｕｉｈｉ — ｒＢｏ ｄｓｆ ｒｔ ｒ ｅ Ｄｉｔｎｇ ｓ ｎｇ Ｅｄｇ ｅＣｈｒ ｍ ａ ｉ ｏ ｔｃ Ｎｕｍ ｂｅ ｓａ ｒｅ Ｄｉｔｎｇ ｓ ｉ — ｔ ｌＣｈｒ ｍ ａ ｉ ｕ ｂｅ ｓ ｒ ｎｄ Ｖｅ ｔｘ— ｓｉ ｕｉｈ ｎｇ Ｔｏ ａ ｏ ｔｃＮ ｍ ｒ
该 引 理 多 用 于 是 正 整 数 值 且 Ｅ ） ， 有 （ ＜１ 则
尸， ＝０＞０ ． （ ） ．
不 等 式 ：Ｐ （ ｒＸ￣Ｏ ≤Ｅ Ｘ）， 以 只 需 证 Ｅ Ｘ） ） （ 所 （ ＋
（ ） 即可 ． ｙ＜１
由概 率论知识 可 知
厂 、 厂 ｔ ／ 、
首先 ， 计算
区 别 的 边 色数 ， ≤ ｎ （ 一１ ， ｎ≥ ３， （ Ｇ） Ａ ｎ ） 当 △≥ １ ， 点 可 区 别 的 全 色数 ｚ Ｇ） ２ Ａ ｎ ） 时 其 ， ≤ ｎ （ 一１ ． （ 关 键 词 ：边 染 色 ； 令染 色 ；点 可 Ｉ 边 色 数 ；点 可 区别 全 色数 ；慨 率 方 法 别 中 图分 类 号 ：Ｏ１７５ ５． 文 献 标 志 码 ：Ａ 文章 编 号 ：ｌ ７—５ ０ ２ １） １０ ７ —４ ６ ２６ １ （０ １０ —０ ５０
｛ ＝０ ， ，＝０ 且 ＝｛ ｝ Ａ ＝｛ ， ｝， ＞０ ＝ ｛＞０ ） ）， ｙ ｝， 即只需 证 尸 （ ｒ ＞０ ＋Ｐ （＞Ｏ＜Ｉ ） ｒＹ ） 即可 ． 又根 据 Ｍａｋ ｖ ｒｏ
引理 １］ （ 一矩量原理 ） 【 ９ 第 如果 Ｅ Ｘ） ， （ ≤ｔ 则
（ ≤ ，＞０ ） ．
・
７ ・ ６
天津科 技大 学学报 第 ２ 卷 第 １ ６ 期 （ 正常 ） 边染 色 ， 须使 以下两 点成立 ： 必 （） 常边染 色 ， １正
（） 意两个点 点可 区别 ． ２任 为此 ， 义如 下指标 变量 ： 定
度 ， ＸＡＧ ： Ｇ ， 则 ｖ ） （ ） 或者 （ ） （ ＋１ ＇ Ｇ ＝ Ｇ） ．
并令 ＝ ∑ ，， 注意到 即是不满足正常
边染 色 的相邻边 对 的数量 ． （ ） 在两个 点 “ ｖ 令 Ｉ存 Ｉ ，，
ｙ ：
称ｍｎ ｌ ｋ Ｖ Ｔ ｝ ｉｋ ￣ — Ｄ Ｃ 为Ｇ的点可区别全色数， ｛ａ 记
为 （ ． Ｇ）
令 ｎ（ ） 示 Ｇ 的 ｄ度 顶 点 的 个 数 ， ｋ（ ） ａＧ 表 令 ＴＧ ＝
究 图 的染 色 问题 ， 到 了 国 内外学 术 界 的普 遍 关 注 ， 受
个 映 射 ， 得 Ｖ ｖ，Ａ Ｅ （ （≠ｗ ，厂“） （ｗ 使 ｕ Ｉ Ｇ） Ｗ ） ｌ ｖ≠ｆ ｕ ）； （
Ｖ ｖ （ ） ｖ ， （） Ｃ ｖ ， ． ∈ＶＧ （ ≠ ） Ｃｕ ≠ （ 其中 Ｃｕ＝ 厂 ｖ ） （ ｔ（ ） ） Ｉ
ｅ ｇ ｏｏ ｉｇ ｗｉ ｔｍｏ ｔ Ａ（ ｄ ｅｃ ｌｒ ｔ ａ ｓ ｎ ｎ一１ ｃ ｌｒ ｙ ｕ ｉｇ ｔｅ ｆ ｓ ｍｅ ｔｐ ｉｃｐｅａ ｄ Ｍａｋ ｖＳｉｅ ｕ ｌｙ ｏ ｒ ｂ ｂｌ ｔｃ ｎ ｈ ） ｏｏｓｂ ｓｎ ｈ ｉ ｔｍｏ ｎ ｒｎ ｉｌ ｎ ｒ ｏ ’ ｎ ｑ ａｉ ｆｐ ｏ ａ ｉｓｉ ｒ ｔ ｉ
１ （ ） Ｖ （ ） ， ｆ称 为 Ｇ的一 个 ｋ一 可 区别 ， Ｇ， ＠ Ｇ｝ 则 ∈ Ｈ 点
边染色 ， 简记为 ｋ Ｖ Ｅ 称 ｍｎｋＧ — Ｄ Ｃ． ｉ｛ｌ存在 Ｖ Ｅ ｝ 一 Ｄ Ｃ
为 Ｇ 的 点 可 区别 边 色 数 （ 称 为 强 边 色 数 ） 记 为 或 ， （ ）（ Ｇ 或 （ ） ． Ｇ） 显 然 ， 个 图 Ｇ具有 点 可 区别 的边染 色 当且仅 当 一 图 Ｇ是没 有 孤 立边 ， 最 多 有一 个 孤立 点 的 图． 样 且 这 的 图称 为 ｖ ｅ 图． ｄｃ
ｄ ｓｉｇ ｉ ｉｇｔｔｌ ｏｏ ｉｇｗｉ ｔ ｓ ２ Ａ（ ｉｔ ｕｓ ｎ ａ ｌｒ ｔ ａ ｔ ｎ ｎ一１ ｃ ｌｒ． ｎ ｈ ｏ ｃ ｎ ｈ ｍｏ ） ｏｏ ｓ
Ｋｅ ｙｗｏｒ ｄｓ： ｅ ｅ ｏｌ ｉ ｄｇ ｃ ｏｒｎｇ； ｔ ｔ ｌ ｏｌ ｉ ｏ ａ ｃ ｏｒｎｇ； ｖｅ ｅ ｄ ｓｉ ｕｉｈ ｎ ｅ ｇｅ ｈ ｏｍ ａｉ ｎ ｔ ｒ ｘ ｉｔｎｇ ｓ ｉ ｇ ｄ ｃ ｒ ｔｃ ｕｍｂｅ ｒ； ｖ ｒｅ ｄｉｔｎ ｉｈｉ ｔ ｔ ｌ ｅ ｘ ｔ ｓｉ ｇｕ ｓ ｎｇ ｏ ａ ｃ ｏ ａ ｉ ｕｍ ｂ ｒ ｐｒ ｂａ ｌｓｉ ｅｈｏ ｈｒ ｍ ｔｃｎ ｅ； ｏ ｂｉｉｔｃｍ ｔ ｄ
２ ｄ（ ｎ ｎ—ｎ ２
１
确 定一 般 图的点可 区别 边 （ ） 数 的上 界 ， 全 色 对于 特殊 图的点 可 区别 边 （ 色 数 的确 定 ， 全） 具有 非常 重要
并令Ｙ ∑ ＝
， 注意到Ｙ即是不满足任意两
点点可 区别 的点 对 的数量 ． 现 只要证 （ ＝０ 且Ｙ：０＞０， 根据事 实 １ ） 又 可得 Ｐ （ ＝Ｏ ， ０ ≥１ ［ Ｊ Ｊ 且）＝ ） 一 Ｐ （ ） 一， ｏ ＞０（ ４ ＝ ＞０＋ （＝ ） 】＞ 】 令