点染色和边赋权
Vertex-Colors and Edge-Weights

作者: 张慧娟 :浙江师范大学,浙江 金华;

关键词: 平面图连通图边赋权顶点染色Tree Planer Graph Connected Graph Edge Weighting Vertex Coloring

摘要:
Lyngsie,Thomassen和Zhong 在1-2-3-猜想的基础上提出了一个强化4-色定理的猜想:对于任意不含孤立边的平面图G,存在G的一个边赋权,使得对任意相邻的两个顶点u,v,有 我们称满足上述条件的边赋权w为G的一个3-边赋权4-染色。这是一个比4-色定理强很多的猜想。在本文中我们证明了阶数至少为3的树满足这个猜想。另外,利用4-色定理,我们证明了每一个平面图 存在一个4-边赋权4-染色。

Abstract: Lyngsie, Thomassen and Zhong on the base of 1-2-3-conjection proposed a conjecture that strengthens the four-color theorem: Every graph G with no isolated edges has a mapping , so that for any two adjacent vertices u and v, We say satisfy the above conditions edge weighting w is 3-edge weighting 4-coloring of a graph G. 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.

1. 引言

对于图的边赋权染色的概念是Karoński,Luczak和Thomason [2] 在2004年引进的。Karoński,Luczak和Thomason在 [2] 中提出如下猜想:对任意不含孤立边的图 G ,存在 G 的一个边赋权 w : E ( G ) { 1 , 2 , 3 } ,使得对任意相邻的两个顶点 u , v ,有 e E ( u ) w ( e ) e E ( v ) w ( e ) 。这一猜想近十多年来受到极大的关注,被称为1-2-3-猜想。我们称满足上述条件的边赋权 w G 的一个3-边赋权顶点染色。设 w : E ( G ) { 1 , 2 , , k } 的一个映射,我们称 w G 的一个 k -边赋权。对于 G 的顶点 v e E ( v ) w ( e ) v 相对于 w 的加权点度。如果对 G 的任意两个相邻的顶点 u , v e E ( u ) w ( e ) e E ( v ) w ( e ) ,称 w G 的一个 k -边赋权顶点染色。

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:设 T 是一个阶数至少为3的树,则存在一个3-边赋权 w : E ( T ) { 1 , 2 , 3 } ,使得对任意两个 u v E ( T ) e E ( u ) w ( e ) e E ( v ) w ( e ) ( mod 4 )

定理2:至少三个顶点的平面图 G ,令 c : V ( G ) { 0 , 1 , 2 , 3 } 。若 v V ( G ) c ( v ) 是偶数,那么存在一个3-边赋权 w : E ( G ) { 1 , 2 , 3 } ,使得对任意两个相邻的两个顶点 u , v e E ( u ) w ( e ) e E ( v ) w ( e ) ( mod 4 )

2. 定理1的证明

为了证明定理1,我们将证明一个更强的定理如下:

定理3:令 T 是树。假设 L T 的一个列表分配,如下:

L ( v ) = { 1 , 2 , 3 } ,如果 v T 的叶子点;

L ( v ) = { 0 , 1 , 2 , 3 } ,否则。

那么存在一个边赋权 w : E ( T ) { 1 , 2 , 3 } ,使得对任意的点 v

e E ( v ) w ( e ) c ( v ) ( mod 4 )

c T 的一个好的点染色, c ( v ) L ( v )

我们通过 V ( T ) 上的归纳假设证明了这一点。如果 | V ( T ) | = 3 ,那么很容易证明定理3。假设 | V ( T ) | 4 n < | V ( T ) | 时,定理3成立。令 u 是树 T 的叶子点, u u * E ( T ) 。因为 T 不包含 K 2 ,所以 d ( u * ) 2 。于是接下来的证明我们分两种情况: d ( u * ) = 2 以及 d ( u * ) 3

Case 1: d ( u * ) = 2

T = T u ,由归纳假设对任意的点 v V ( T ) 存在一个边赋权 w : E ( T ) { 1 , 2 , 3 } e E ( v ) w ( e ) c ( v ) ( mod 4 )

并且 c T 的一个好的染色 c ( v ) L ( v ) ,其中对任意的 v V ( T ) { u * } L ( v ) = L ( v ) ,且 L ( u * ) = { 1 , 2 , 3 } 。令 u * * u u * 的一个邻点。定义 T 的一个边赋权 w : E ( T ) { 1 , 2 , 3 } :使得如果 e E ( T ) ,那么 w ( e ) = w ( e ) ,而 w ( u u * ) 定义如表1

Table 1. The definition of w ( u u * )

表1. w ( u u * ) 的定义

不难发现 w T 的一个边赋权,使得对 v V ( T ) ,有

e E ( v ) w ( e ) c ( v ) ( mod 4 )

c T 的一个好的染色, c ( v ) L ( v )

Case 2: d ( u * ) 3

用集合 S 表示 T 的所有叶子点,即 S = { v : v T } 。令 N ( S ) = { v * : v v * E ( T ) , v S } 。注意对任意的 v * N ( S ) d ( v * ) 3 。如果对任意的 v * N ( S ) ,在 T v * 只有一个叶子点邻点,那么 T 的平均度 d ¯ ( T ) 2 ,即 | E ( T ) | | V ( T ) | ,与 T 是树相矛盾。因此, N ( S ) 中存在一个顶点,不失一般性地 u * N ( S ) ,使得 u * T 中至少有两个叶子点邻点,记作 u u 1 。令 T = T { u , u 1 } ,由归纳假设使对每一个点 v V ( T ) 存在一个边赋权 w : E ( T ) { 1 , 2 , 3 }

e E ( v ) w ( e ) c ( v ) ( mod 4 )

使得 c ( v ) L ( v ) c T 的一个好的染色。其中 L 的定义如下:

如果 d ( u * ) = 3 ,那么 L ( u * ) = { 1 , 2 , 3 } ,对任意的点 v V ( T ) { u * } L ( v ) = L ( v ) ;如果 d ( u * ) 4 ,那么对任意的点 v V ( T ) L ( v ) = L ( v )

定义边赋权 w : E ( T ) { 1 , 2 , 3 } :如果 e E ( T ) ,那么 w ( e ) = w ( e ) ;这时我们定义 w ( u * u 1 ) w ( u * u ) 如下:如果 c ( u * ) 2 那么 w ( u * u 1 ) = w ( u * u ) = 2 ;否则, w ( u * u 1 ) = 1 w ( u * u ) = 3 。注意对于每个点 v V ( T ) c ( v ) c ( v ) ( mod 4 ) 。此外,因为 c ( v ) = c ( v ) + w ( u * u 1 ) + w ( u * u ) ,它验证了 c ( u 1 ) c ( u * ) , c ( u ) c ( u * ) ( mod 4 ) 。因此, w T 中对于每个点 v 的一个边赋权染色,

e E ( v ) w ( e ) c ( v ) ( mod 4 )

并且 c T 的一个好的染色, c ( v ) L ( v ) 。证毕。

3. 定理2的证明

定理2也可以表述为:

定理4:令 Γ 是四阶循环群,令 G 是非平凡的平面图。那么存在一个边赋权 w : E ( G ) Γ 使得 c 是一个好的点染色,其中 c ( v ) = e E ( v ) w ( e )

因为 Γ 是循环群,由同构的性质我们可以假设 Γ = { g 1 , g 2 , g 3 , g 4 } = { 0 , 1 , 2 , 3 } 。由四色定理,我们可以用四种颜色将一个平面图 G 染好。对于 1 i 4 我们假设第 i 个颜色包含 n i 0 个点。

Case 1:如果图 G 是二部图。

如果二部图 G 是星图 K 1 , t ,那么令 v K 1 , t 中不是叶子的点,用 v 1 , v 2 , , v t 表示 K 1 , t 的叶子点,其中 t 是正整数且 t 2 。如果 t 4 p + 1 ,那么对所有的边 e E ( G ) w ( e ) = 1 。如果 t = 4 p + 1 ,那么对于 i 4 p 1 时,令 w ( v v i ) = 1 ;和 w ( v v 4 p ) = w ( v v 4 p + 1 ) = 2 ,这证明了 c 是图 G 的一个好的染色。

假设 G 不是星图。

首先,令 c 0 : V ( G ) { 0 , 1 } ,对于 1 i 2 我们假设第 i 个颜色类包含 n i 0 个点。然后我们定义权重 w : E ( G ) { 0 , 1 , 2 , 3 } 。当 c 0 e E ( v ) w ( e ) 时我们说这个点是错误的点;且当 c 0 = e E ( v ) w ( e ) 时我们说这个点是正确的点。我们想要实现图 G 中的每个顶点都是正确的顶点。

最初,我们定义图 G 的每条边的权重为0,即对于任意的 e E ( G ) w 0 0 。因为图 G 是非平凡图,那么由对称性,我们可以在颜色类1中选择一个点 x 以及 d ( x ) 2 。所以颜色类1中的每个点都是错误的点,因为 c 0 = 1 0 = e E ( v ) w ( e )

现在我们尝试修改权重:选择一个从错误的点 u g = e E ( u ) w ( e ) 到另一个错误的点 v 的偶长途径。遍历这个途径,给途径上的边交替增加 1 g , g 1 , 。这个操作保持了顶点权重的总和,除了点 u 和点 v 其他所有点的权重不变,并且生成了一个正确的点。

如果图 G 中的每个点都是正确的点,那么证毕。否则,存在一个点是错误的点,并且记这个错误的点 x 是颜色类1中的点。因为颜色类0中的点是正确的点,那么 x 的权重 g = 1 n 2 。如果 g 0 ,那么证毕。否则我们可以将与 x 相关联的两条边分别加权重2和3。因此,我们得到了边赋权 w 和好的染色 c 。那么证毕。

Case 2:如果图 G 是非二部图。

c : V ( G ) { 0 , 1 , 2 , 3 } = { g 1 , g 2 , g 3 , g 4 } 是一个好的点染色。通过置换颜色类,我们可以假设顶点颜色的总和是偶数,假设 v V ( G ) c ( v ) = 2 h 。令其中一条边的权重为 h ( mod 4 ) 和剩余其他边的权重为0,所以顶点权重的总和是 2 h n 1 g 1 + n 2 g 2 + n 3 g 3 + n 4 g 4 = 2 h 。我们现在尝试修改权重,使得顶点的权重总和不变,直到所有染颜色 i 的顶点有权重 g i , 1 i 4 。假设存在一个染颜色 i 的顶点 u 有错误的权重 g g i ;因为 n 1 g 1 + n 2 g 2 + n 3 g 3 + n 4 g 4 = 2 h 那么存在另一个顶点 v V ( G ) 的权重也是错误的,选择一个从 u v 的偶长途径,这总是可以存在的,除非图 G 是二部图。遍历这个途径,给途径上的边交替增加 g i g , g g i , g i g , g g i , 。这个操作保持点的权重的总和,除了点 u 和点 v 其他所有点的权重不变,并且生成了一个正确的点。因此,重复的应用以上操作给出所需的权重。定理证毕。

如果 | Γ | = 2 ,那么定理4可能会不满足。例如星图 K 1 , 3 不可以用整数模2赋权。

文章引用: 张慧娟 (2019) 点染色和边赋权。 应用数学进展, 8, 664-668. doi: 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

分享
Top