点染色和边赋权

Vertex-Colors and Edge-Weights

摘要: 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\left(G\right)\to \left\{1,2,3\right\}$，使得对任意相邻的两个顶点 $u,v$，有 ${\displaystyle \underset{e\in E\left(u\right)}{\sum }w\left(e\right)}\ne {\displaystyle \underset{e\in E\left(v\right)}{\sum }w\left(e\right)}$。这一猜想近十多年来受到极大的关注，被称为1-2-3-猜想。我们称满足上述条件的边赋权 $w$ 为 $G$ 的一个3-边赋权顶点染色。设 $w:E\left(G\right)\to \left\{1,2,\cdots ,k\right\}$ 的一个映射，我们称 $w$ 为 $G$ 的一个 $k$ -边赋权。对于 $G$ 的顶点 $v$， ${\displaystyle \underset{e\in E(v)}{\sum }w\left(e\right)}$ 为 $v$ 相对于 $w$ 的加权点度。如果对 $G$ 的任意两个相邻的顶点 $u,v$， ${\displaystyle \underset{e\in E\left(u\right)}{\sum }w\left(e\right)}\ne {\displaystyle \underset{e\in E\left(v\right)}{\sum }w\left(e\right)}$，称 $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\left(T\right)\to \left\{1,2,3\right\}$，使得对任意两个 $uv\in E(T)$， ${\displaystyle \underset{e\in E\left(u\right)}{\sum }w\left(e\right)}\ne {\displaystyle \underset{e\in E\left(v\right)}{\sum }w\left(e\right)}\left(\mathrm{mod}4\right)$。

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

2. 定理1的证明

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

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

$L\left(v\right)=\left\{1,2,3\right\}$，如果 $v$ 是 $T$ 的叶子点；

$L\left(v\right)=\left\{0,1,2,3\right\}$，否则。

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

${\displaystyle \underset{e\in E\left(v\right)}{\sum }w\left(e\right)}\equiv c\left(v\right)\left(\mathrm{mod}4\right)$，

且 $c$ 是 $T$ 的一个好的点染色， $c\left(v\right)\in L\left(v\right)$。

我们通过 $V\left(T\right)$ 上的归纳假设证明了这一点。如果 $\left|V\left(T\right)\right|=3$，那么很容易证明定理3。假设 $\left|V\left(T\right)\right|\ge 4$ 且 $n^{\prime }<\left|V\left(T\right)\right|$ 时，定理3成立。令 $u$ 是树 $T$ 的叶子点， $u{u}^{*}\in E\left(T\right)$。因为 $T$ 不包含 $K_2$，所以 $d\left(u^{*}\right)\ge 2$。于是接下来的证明我们分两种情况： $d\left(u^{*}\right)=2$ 以及 $d\left(u^{*}\right)\ge 3$。

Case 1： $d\left(u^{*}\right)=2$。

令 $T^{\prime }=T-u$，由归纳假设对任意的点 $v\in V\left(T^{\prime }\right)$ 存在一个边赋权 $w^{\prime }:E\left(T^{\prime }\right)\to \left\{1,2,3\right\}$， ${\displaystyle \underset{e\in E\left(v\right)}{\sum }{w}^{\prime }\left(e\right)}\equiv c^{\prime }\left(v\right)\left(\mathrm{mod}4\right)$。

并且 $c^{\prime }$ 是 $T^{\prime }$ 的一个好的染色 $c^{\prime }\left(v\right)\in L^{\prime }\left(v\right)$，其中对任意的 $v\in V\left(T^{\prime }\right)-\left\{u^{*}\right\}$ 时 $L^{\prime }(v)=L\left(v\right)$，且 $L^{\prime }\left(u^{*}\right)=\left\{1,2,3\right\}$。令 $u^{**}\ne u$ 是 $u^{*}$ 的一个邻点。定义 $T$ 的一个边赋权 $w:E\left(T\right)\to \left\{1,2,3\right\}$ ：使得如果 $e\in E\left(T^{\prime }\right)$，那么 $w\left(e\right)=w^{\prime }\left(e\right)$，而 $w\left(u{u}^{*}\right)$ 定义如表1。

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

表1. $w\left(u{u}^{*}\right)$ 的定义

不难发现 $w$ 是 $T$ 的一个边赋权，使得对 $\forall$ $v\in V\left(T\right)$，有

${\displaystyle \underset{e\in E\left(v\right)}{\sum }w\left(e\right)}\equiv c\left(v\right)\left(\mathrm{mod}4\right)$

$c$ 是 $T$ 的一个好的染色， $c\left(v\right)\in L\left(v\right)$。

Case 2： $d\left(u^{*}\right)\ge 3$。

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

${\displaystyle \underset{e\in E\left(v\right)}{\sum }{w}^{\prime }\left(e\right)}\equiv c^{\prime }\left(v\right)\left(\mathrm{mod}4\right)$，

使得 $c^{\prime }\left(v\right)\in L^{\prime }\left(v\right)$ 且 $c^{\prime }$ 是 $T^{\prime }$ 的一个好的染色。其中 $L^{\prime }$ 的定义如下：

如果 $d\left(u^{*}\right)=3$，那么 $L^{\prime }\left(u^{*}\right)=\left\{1,2,3\right\}$，对任意的点 $v\in V\left(T^{\prime }\right)-\left\{u^{*}\right\}$ 有 $L^{\prime }\left(v\right)=L\left(v\right)$ ；如果 $d\left(u^{*}\right)\ge 4$，那么对任意的点 $v\in V\left(T^{\prime }\right)$ 有 $L^{\prime }\left(v\right)=L\left(v\right)$。

定义边赋权 $w:E\left(T\right)\to \left\{1,2,3\right\}$ ：如果 $e\in E\left(T^{\prime }\right)$，那么 $w\left(e\right)=w^{\prime }\left(e\right)$ ；这时我们定义 $w\left(u*u_1\right)$ 和 $w\left(u*u\right)$ 如下：如果 $c^{\prime }\left(u^{*}\right)\ne 2$ 那么 $w\left(u*u_1\right)=w\left(u*u\right)=2$ ；否则， $w\left(u*u_1\right)=1$， $w\left(u*u\right)=3$。注意对于每个点 $v\in V\left(T^{\prime }\right)$， $c^{\prime }\left(v\right)\equiv c\left(v\right)\left(\mathrm{mod}4\right)$。此外，因为 $c\left(v\right)=c^{\prime }\left(v\right)+w\left(u*u_1\right)+w\left(u*u\right)$，它验证了 $c\left(u_1\right)\ne c\left(u^{*}\right),c\left(u\right)\ne c\left(u^{*}\right)\left(\mathrm{mod}4\right)$。因此， $w$ 是 $T$ 中对于每个点 $v$ 的一个边赋权染色，

${\displaystyle \underset{e\in E\left(v\right)}{\sum }w\left(e\right)}\equiv c\left(v\right)\left(\mathrm{mod}4\right)$，

并且 $c$ 是 $T$ 的一个好的染色， $c\left(v\right)\in L\left(v\right)$。证毕。

3. 定理2的证明

定理2也可以表述为：

定理4：令 $\Gamma$ 是四阶循环群，令 $G$ 是非平凡的平面图。那么存在一个边赋权 $w:E\left(G\right)\to \Gamma$ 使得 $c$ 是一个好的点染色，其中 $c\left(v\right)={\displaystyle \underset{e\in E\left(v\right)}{\sum }w\left(e\right)}$。

因为 $\Gamma$ 是循环群，由同构的性质我们可以假设 $\Gamma =\left\{g_1,g_2,g_3,g_4\right\}=\left\{0,1,2,3\right\}$。由四色定理，我们可以用四种颜色将一个平面图 $G$ 染好。对于 $1\le i\le 4$ 我们假设第 $i$ 个颜色包含 $n_i\ge 0$ 个点。

Case 1：如果图 $G$ 是二部图。

如果二部图 $G$ 是星图 $K_{1,t}$，那么令 $v$ 是 $K_{1,t}$ 中不是叶子的点，用 $v_1,v_2,\cdots ,v_t$ 表示 $K_{1,t}$ 的叶子点，其中 $t$ 是正整数且 $t\ge 2$。如果 $t\ne 4p+1$，那么对所有的边 $e\in E\left(G\right)$ 令 $w\left(e\right)=1$。如果 $t=4p+1$，那么对于 $i\le 4p-1$ 时，令 $w\left(v{v}_i\right)=1$ ；和 $w\left(v{v}_{4p}\right)=w\left(v{v}_{4p+1}\right)=2$，这证明了 $c$ 是图 $G$ 的一个好的染色。

假设 $G$ 不是星图。

首先，令 $c_0:V\left(G\right)\to \left\{0,1\right\}$，对于 $1\le i\le 2$ 我们假设第 $i$ 个颜色类包含 $n_i\ge 0$ 个点。然后我们定义权重 $w:E\left(G\right)\to \left\{0,1,2,3\right\}$。当 $c_0\ne {\displaystyle \underset{e\in E\left(v\right)}{\sum }w\left(e\right)}$ 时我们说这个点是错误的点；且当 $c_0={\displaystyle \underset{e\in E\left(v\right)}{\sum }w\left(e\right)}$ 时我们说这个点是正确的点。我们想要实现图 $G$ 中的每个顶点都是正确的顶点。

最初，我们定义图 $G$ 的每条边的权重为0，即对于任意的 $e\in E\left(G\right)$ 有 $w_0\equiv 0$。因为图 $G$ 是非平凡图，那么由对称性，我们可以在颜色类1中选择一个点 $x$ 以及 $d\left(x\right)\ge 2$。所以颜色类1中的每个点都是错误的点，因为 $c_0=1\ne 0={\displaystyle \underset{e\in E\left(v\right)}{\sum }w\left(e\right)}$。

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

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

Case 2：如果图 $G$ 是非二部图。

令 $c:V\left(G\right)\to \left\{0,1,2,3\right\}=\left\{g_1,g_2,g_3,g_4\right\}$ 是一个好的点染色。通过置换颜色类，我们可以假设顶点颜色的总和是偶数，假设 ${\displaystyle \underset{v\in V\left(G\right)}{\sum }c\left(v\right)}=2h$。令其中一条边的权重为 $h\left(\mathrm{mod}4\right)$ 和剩余其他边的权重为0，所以顶点权重的总和是 $2h$ 且 $n_1{g}_1+n_2{g}_2+n_3{g}_3+n_4{g}_4=2h$。我们现在尝试修改权重，使得顶点的权重总和不变，直到所有染颜色 $i$ 的顶点有权重 $g_i,1\le i\le 4$。假设存在一个染颜色 $i$ 的顶点 $u$ 有错误的权重 $g\ne g_i$ ；因为 $n_1{g}_1+n_2{g}_2+n_3{g}_3+n_4{g}_4=2h$ 那么存在另一个顶点 $v\in V\left(G\right)$ 的权重也是错误的，选择一个从 $u$ 到 $v$ 的偶长途径，这总是可以存在的，除非图 $G$ 是二部图。遍历这个途径，给途径上的边交替增加 $g_i-g,g-g_i,g_i-g,g-g_i,\cdots$。这个操作保持点的权重的总和，除了点 $u$ 和点 $v$ 其他所有点的权重不变，并且生成了一个正确的点。因此，重复的应用以上操作给出所需的权重。定理证毕。

如果 $\left|\Gamma \right|=2$，那么定理4可能会不满足。例如星图 $K_{1,3}$ 不可以用整数模2赋权。