Advances in Applied Mathematics
Vol.
08
No.
04
(
2019
), Article ID:
29802
,
5
pages
10.12677/AAM.2019.84074
Vertex-Colors and Edge-Weights
Huijuan Zhang
Zhejiang Normal University, Jinhua Zhejiang
Received: Mar. 31st, 2019; accepted: Apr. 15th, 2019; published: Apr. 22nd, 2019
ABSTRACT
Lyngsie, Thomassen and Zhong [1] on the base of 1-2-3-conjection proposed a conjecture that strengthens the four-color theorem: Every graph with no isolated edges has a mapping , so that for any two adjacent vertices , We say satisfy the above conditions edge weighting is 3-edge weighting 4-coloring of a graph . This conjecture is considerably stronger than the four-color theorem. In this paper, we prove that Lyngsie, Thomassen and Zhong conjecture holds for trees. By using the four-color theorem, we prove that every planar graph has a 4-edge weighting 4-coloring.
Keywords:Tree, Planer Graph, Connected Graph, Edge Weighting Vertex Coloring
点染色和边赋权
张慧娟
浙江师范大学,浙江 金华
收稿日期:2019年3月31日;录用日期:2019年4月15日;发布日期:2019年4月22日
摘 要
Lyngsie,Thomassen和Zhong [1] 在1-2-3-猜想的基础上提出了一个强化4-色定理的猜想:对于任意不含孤立边的平面图 ,存在 的一个边赋权 ,使得对任意相邻的两个顶点 ,有 我们称满足上述条件的边赋权 为 的一个3-边赋权4-染色。这是一个比4-色定理强很多的猜想。在本文中我们证明了阶数至少为3的树满足这个猜想。另外,利用4-色定理,我们证明了每一个平面图 存在一个4-边赋权4-染色。
关键词 :树,平面图,连通图,边赋权顶点染色
Copyright © 2019 by author and Hans Publishers Inc.
This work is licensed under the Creative Commons Attribution International License (CC BY).
http://creativecommons.org/licenses/by/4.0/
1. 引言
对于图的边赋权染色的概念是Karoński,Luczak和Thomason [2] 在2004年引进的。Karoński,Luczak和Thomason在 [2] 中提出如下猜想:对任意不含孤立边的图 ,存在 的一个边赋权 ,使得对任意相邻的两个顶点 ,有 。这一猜想近十多年来受到极大的关注,被称为1-2-3-猜想。我们称满足上述条件的边赋权 为 的一个3-边赋权顶点染色。设 的一个映射,我们称 为 的一个 -边赋权。对于 的顶点 , 为 相对于 的加权点度。如果对 的任意两个相邻的顶点 ,,称 为 的一个 -边赋权顶点染色。
Karoński,Luczak和Thomason证明了没有孤立边的3-可染的连通图满足1-2-3-猜想。2010年 Kalkowski,Karoński和Pfender [3] 证明了没有孤立边的连通图,存在一个5-边赋权染色。2017年,Wu,Zhang和Zhu [4] 等人证明了4-可染的4-边连通图存在3-边赋权染色。Lyngsie,Thomassen和Zhong [1] 提出了强化4-色定理的猜想。Lyngsie等人证明了4-可染的4-边连通图和三角化的平面图满足这个猜想。
在本文中我们证明了:
定理1:设 是一个阶数至少为3的树,则存在一个3-边赋权 ,使得对任意两个 ,。
定理2:至少三个顶点的平面图 ,令 。若 是偶数,那么存在一个3-边赋权 ,使得对任意两个相邻的两个顶点 ,。
2. 定理1的证明
为了证明定理1,我们将证明一个更强的定理如下:
定理3:令 是树。假设 是 的一个列表分配,如下:
,如果 是 的叶子点;
,否则。
那么存在一个边赋权 ,使得对任意的点 有
,
且 是 的一个好的点染色, 。
我们通过 上的归纳假设证明了这一点。如果 ,那么很容易证明定理3。假设 且 时,定理3成立。令 是树 的叶子点, 。因为 不包含 ,所以 。于是接下来的证明我们分两种情况: 以及 。
Case 1: 。
令 ,由归纳假设对任意的点 存在一个边赋权 ,。
并且 是 的一个好的染色 ,其中对任意的 时 ,且 。令 是 的一个邻点。定义 的一个边赋权 :使得如果 ,那么 ,而 定义如表1。
Table 1. The definition of w ( u u * )
表1. 的定义
不难发现 是 的一个边赋权,使得对 ,有
是 的一个好的染色, 。
Case 2: 。
用集合 表示 的所有叶子点,即 。令 。注意对任意的 有 。如果对任意的 ,在 中 只有一个叶子点邻点,那么 的平均度 ,即 ,与 是树相矛盾。因此, 中存在一个顶点,不失一般性地 ,使得 在 中至少有两个叶子点邻点,记作 和 。令 ,由归纳假设使对每一个点 存在一个边赋权 ,
,
使得 且 是 的一个好的染色。其中 的定义如下:
如果 ,那么 ,对任意的点 有 ;如果 ,那么对任意的点 有 。
定义边赋权 :如果 ,那么 ;这时我们定义 和 如下:如果 那么 ;否则, ,。注意对于每个点 ,。此外,因为 ,它验证了 。因此, 是 中对于每个点 的一个边赋权染色,
,
并且 是 的一个好的染色, 。证毕。
3. 定理2的证明
定理2也可以表述为:
定理4:令 是四阶循环群,令 是非平凡的平面图。那么存在一个边赋权 使得 是一个好的点染色,其中 。
因为 是循环群,由同构的性质我们可以假设 。由四色定理,我们可以用四种颜色将一个平面图 染好。对于 我们假设第 个颜色包含 个点。
Case 1:如果图 是二部图。
如果二部图 是星图 ,那么令 是 中不是叶子的点,用 表示 的叶子点,其中 是正整数且 。如果 ,那么对所有的边 令 。如果 ,那么对于 时,令 ;和 ,这证明了 是图 的一个好的染色。
假设 不是星图。
首先,令 ,对于 我们假设第 个颜色类包含 个点。然后我们定义权重 。当 时我们说这个点是错误的点;且当 时我们说这个点是正确的点。我们想要实现图 中的每个顶点都是正确的顶点。
最初,我们定义图 的每条边的权重为0,即对于任意的 有 。因为图 是非平凡图,那么由对称性,我们可以在颜色类1中选择一个点 以及 。所以颜色类1中的每个点都是错误的点,因为 。
现在我们尝试修改权重:选择一个从错误的点 且 到另一个错误的点 的偶长途径。遍历这个途径,给途径上的边交替增加 。这个操作保持了顶点权重的总和,除了点 和点 其他所有点的权重不变,并且生成了一个正确的点。
如果图 中的每个点都是正确的点,那么证毕。否则,存在一个点是错误的点,并且记这个错误的点 是颜色类1中的点。因为颜色类0中的点是正确的点,那么 的权重 。如果 ,那么证毕。否则我们可以将与 相关联的两条边分别加权重2和3。因此,我们得到了边赋权 和好的染色 。那么证毕。
Case 2:如果图 是非二部图。
令 是一个好的点染色。通过置换颜色类,我们可以假设顶点颜色的总和是偶数,假设 。令其中一条边的权重为 和剩余其他边的权重为0,所以顶点权重的总和是 且 。我们现在尝试修改权重,使得顶点的权重总和不变,直到所有染颜色 的顶点有权重 。假设存在一个染颜色 的顶点 有错误的权重 ;因为 那么存在另一个顶点 的权重也是错误的,选择一个从 到 的偶长途径,这总是可以存在的,除非图 是二部图。遍历这个途径,给途径上的边交替增加 。这个操作保持点的权重的总和,除了点 和点 其他所有点的权重不变,并且生成了一个正确的点。因此,重复的应用以上操作给出所需的权重。定理证毕。
如果 ,那么定理4可能会不满足。例如星图 不可以用整数模2赋权。
文章引用
张慧娟. 点染色和边赋权
Vertex-Colors and Edge-Weights[J]. 应用数学进展, 2019, 08(04): 664-668. https://doi.org/10.12677/AAM.2019.84074
参考文献
- 1. Lyngsie, K.S., Thomassen, C. and Zhong, L. (2018) Four Vertex-Colors and Three Edge-Weights. AMS Subject Clas-sifications, 05C10, 05C15, 05C22.
- 2. Karoński, M., Luczak, T. and Thomason, A. (2004) Edge Weights and Vertex Colours. Journal of Combinatorial Theory, Series B, 91, 151-157. https://doi.org/10.1016/j.jctb.2003.12.001
- 3. Kalkowski, M., Karon’ski, M. and Pfender, F. (2010) Ver-tex-Coloring Edge-Weightings: Towards the 1-2-3-Conjecture. Journal of Combinatorial Theory, Series B, 100, 347-349. https://doi.org/10.1016/j.jctb.2009.06.002
- 4. Wu, Y.Z., Zhang, C.Q. and Zhu, B.X. (2017) Vertex-Coloring 3-Edge-Weighting of Some Graphs. Discrete Mathematics, 340, 154-159. https://doi.org/10.1016/j.disc.2016.08.011