着色问题

边着色问题

图的边着色，本质上是对应实际问题中的“划分”问题或“分类” 问题。

对 $G$ 的边进行着色，若相邻边着不同颜色，则称对 $G$ 进行正常边着色；

在对 $G$ 正常边着色时，着相同颜色的边集称为该正常边着色的一个色组；

如果能用 $k$ 种颜色对图 $G$ 进行正常边着色，称 $G$ 是 $k$ 边可着色的；

对 $G$ 进行正常边着色需要的最少颜色数称为 $G$ 的边色数，记为：

$${\chi }^{\prime }(G)$$

着色需要满足相邻边着不同色，所以很自然地有：(对于无环图)

$${\chi }^{\prime }(G)\ge \mathrm{\Delta }$$

也就是边色数以最大顶点度为下限。

二部图

$${\chi }^{\prime }(K_{m,n})=\mathrm{\Delta }$$

---

证明

假设：

• $n>m$；
• 所以 $\mathrm{\Delta }=n$；
• $X=\{x_0,x_1,\cdots ,x_{m-1}\}$；
• $Y=\{y_0,y_1,\cdots ,y_{n-1}\}$；
• $n$ 个颜色集合为：$\{0,1,2,\cdots ,n-1\}$；

令 $\pi$ 是 $K_{m,n}$ 的一个 $n$ 着色方案，满足：

$$\mathrm{\forall }{x}_i{y}_j\in E(K_{m,n}),\pi (x_i{y}_j)=(i+j)(modn)$$

对 $K_{m,n}$ 中任意两条邻接边 $x_i{y}_j$ 和 $x_i{y}_k$ ，若二者在 $\pi$ 中着色相同，即 $\pi (x_i{y}_j)=\pi (x_i{y}_k)$ ，则有：

$$(i+j)(modn)=(i+k)(modn)\Rightarrow j=k$$

于是 $x_i{y}_j=x_i{y}_k$ ，所以 $\pi$ 是一个正常的 $n$ 着色（满足相邻边着不同色）。也即 $(X,Y)$ 是 $n$ 可着色的。

同时 ${\chi }^{\prime }(K_{m,n})\ge \mathrm{\Delta }=n$ ，所以 ${\chi }^{\prime }(K_{m,n})=n$。

偶图(哥尼定理)

偶图 $G$ 的边色数：

$${\chi }^{\prime }(G)=\mathrm{\Delta }$$

---

证明可利用数学归纳法

当 $m=1$ 时，$\mathrm{\Delta }=1$，有 ${\chi }^{\prime }(G)=\mathrm{\Delta }=1$ 成立。

设对于小于 $m$ 条边的偶图来说命题成立。

设 $G$ 是具有 $m$ 条边的偶图。

取 $uv\in G$ , 考虑 $G_1=G-uv$, 由归纳假设有:

$${\chi }^{\prime }(G_1)=\mathrm{\Delta }(G_1)\le \mathrm{\Delta }(G)$$

这说明， $G$ 存在一种 $\mathrm{\Delta }(G)$ 边着色方案 $\pi$ . 对于该着色方案，因为 $uv$ 未着色，所以点 $u$ 与 $v$ 均至少缺少一种色。

---

情形 1：如果 $u$ 与 $v$ 均缺同一种色 $i$。

则在 $G_1+uv$ 中给 $uv$ 着色 $i$ , 而 $G$ 其它边按 $\pi$ 方案着色。这样得到 $G$ 的 $\mathrm{\Delta }$ 着色方案，所以: ${\chi }^{\prime }(G)=\mathrm{\Delta }$。

---

情形 2：如果 $u$ 缺色 $i$ , 而 $v$ 缺色 $j$ , 但不缺色 $i$。

设 $H(i,j)$ 表示 $G$ 中由 $i$ 色边与 $j$ 色边导出的子图。显然，该图每个分支是 $i$ 色边和 $j$ 色边交替出现的路或圈。 对于 $H(i,j)$ 中含点 $v$ 的分支来说，因 $v$ 缺色 $j$ , 但不缺色 $i$ , 所以，在 $H(i,j)$ 中，点 $v$ 的度数为 1。这说明，$H(i,j)$ 中含 $v$ 的分支是一条路 $P$ . 进一步地，我们可以说明，上面的路 $P$ 不含点 $u$ .因为，如果 $P$ 含有点 $u$ , 那么 $P$ 必然是一条长度为偶数的路，这样，$P+uv$ 是 $G$ 中的奇圈，这与 $G$ 是偶图矛盾!

既然 $P$ 不含点 $u$ , 所以我们可以交换 $P$ 中着色，而不破坏 $G_1$ 的正常边着色。但交换着色后，$v$ 就变成缺色 $j$ , 但不缺色 $i$，$u$ 与 $v$ 均缺色 $i$ , 于是由情形 1, 可以得到 $G$ 的 $\mathrm{\Delta }$ 正常边着色，即证明 ${\chi }^{\prime }(G)=\mathrm{\Delta }$。

一般简单图

引理

设 $G$ 是简单图，$x$ 与 $y$ 是 $G$ 中两个不相邻的顶点，$\pi$ 是 $G$ 的一个正常 $k$ 边着色。若对该着色，$x,y$ 以及与 $x$ 相邻的点均至少缺少一种颜色，则 $G+xy$ 也是 $k$ 边可着色的

维津定理(Vizing)

若图 $G$ 是简单图，则 ${\chi }^{\prime }(G)=\mathrm{\Delta }$ 或 ${\chi }^{\prime }(G)=\mathrm{\Delta }+1$。

---

只需要证明 ${\chi }^{\prime }(G)\le \mathrm{\Delta }+1$ 即可。 对 $G$ 的边数 $m$ 作数学归纳证明。

当 $m=1$ 时，$\mathrm{\Delta }=1$, ${\chi }^{\prime }(G)=1<\Delta +1$。

设当边数少于 $m$ 时，结论成立。下面考虑边数为 $m\ge 2$ 的单图 $G$。

设 $xy\in E(G)$ , 令 $G_1=G-xy$. 由归纳假设有:

$${\chi }^{\prime }(G_1)\le \mathrm{\Delta }(G_1)+1\le \mathrm{\Delta }(G)+1$$

于是，存在 $G_1$ 的 $\mathrm{\Delta }(G)+1$ 正常边作色 $\pi$。显然 $G$ 的每个顶点都至少缺少一种颜色。根据引理知 $G+xy$ 是 $\mathrm{\Delta }(G)+1$ 可着色的。即证明: ${\chi }^{\prime }(G)\le \mathrm{\Delta }(G)+1$。

充分条件 1

::: primary 给出了 Vizing 定理结论中 ${\chi }^{\prime }(G)=\mathrm{\Delta }$ 情况的充分条件 设 $G$ 是单图且 $\mathrm{\Delta }(G)>0$。若 $G$ 中只有一个最大度点或恰有两个相邻的最大度点，则:

$${\chi }^{\prime }(G)=\mathrm{\Delta }(G)$$

充分条件 2

::: primary 给出了 Vizing 定理结论中 ${\chi }^{\prime }(G)=\mathrm{\Delta }+1$ 情况的充分条件 设 $G$ 是单图。若点数 $n=2k+1$ 且边数 $m>k\mathrm{\Delta }$，则:

$${\chi }^{\prime }(G)=\mathrm{\Delta }(G)+1$$

---

证明可利用反证法，若不然，由维津定理，${\chi }^{\prime }(G)=\mathrm{\Delta }(G)$。

设 $\pi$ 是 $G$ 的 $\mathrm{\Delta }(G)$ 正常边着色方案，对于 $G$ 的每个色组来说，包含的边数至多 $\frac{n-1}{2}=k$。这样：$m(G)\le \mathrm{\Delta }k$，与条件矛盾。

充分条件 3

::: primary 给出了 Vizing 定理结论中 ${\chi }^{\prime }(G)=\mathrm{\Delta }+1$ 情况的充分条件 设 $G$ 是奇数阶 $\mathrm{\Delta }$ 正则单图，若 $\mathrm{\Delta }>0$，则:

$${\chi }^{\prime }(G)=\mathrm{\Delta }(G)+1$$

---

证明：

设 $n=2k+1$，因 $G$ 是 $\mathrm{\Delta }$ 正则单图，且 $\mathrm{\Delta }>0$，所以：

$$m(G)=\frac{n\mathrm{\Delta }}{2}=\frac{(2k+1)\mathrm{\Delta }}{2}>k\mathrm{\Delta }$$

由定理 ${\chi }^{\prime }(G)=\mathrm{\Delta }(G)+1$。

无环有重边图

维津定理(Vizing)

设无环图 $G$ 中边的最大重数为 $\mu$​，则:

$${\chi }^{\prime }(G)\le \mathrm{\Delta }(G)+\mu$$

其中 $\le$ 边界是紧的，也就是等号是可以相等的。

边着色的应用

排课表问题

$X,Y$ 分别表示教师、教学班的集合：

$$\begin{gathered} X=\{x_1,x_2,\cdots ,x_m\} \\ Y=\{y_1,y_2,\cdots ,y_n\} \end{gathered}$$

$x_i$ 与 $y_j$ 间连 $p_{ij}$ 条边，得二部图 $G=(X,Y)$。

求最少排多少节课的问题，每节课可以有多个教学班同时上课，转化为如何在 $G$ 中将边集 $E$ 划分为互不相交的 $p$ 个匹配，且使得 $p$ 最小

如果每个匹配中的边用同一种颜色着色，不同匹配中的边不同颜色，则问题转化为在 $G$ 中给每条边着色，相邻边着不同色，至少需要的颜色数

比赛安排问题

玩家为顶点，2 个玩家间进行一次比赛为一条边，求最少安排多少场比赛，每场比赛可以有多对玩家同时比赛。

Abstract

基于圈的边着色问题和顶点着色问题是完全等价的，因为边和点可互换。

顶点着色

对图 $G$ 的每个顶点着色，使得相邻顶点着不同颜色，称为对 $G$ 的正常顶点着色；

如果用 $k$ 种颜色可以对 $G$ 进行正常点着色，称 $G$ 是 $k$ 可着色的；

着同一种颜色的顶点集合称为一个色组，它们彼此互不相邻，所有又称为点独立集；

图 $G$ 正常顶点着色需要的最少颜色数，称为图 $G$ 的点色数，简称色数，记为：

$$\chi (G)$$

色数为 $k$ 的图称为 $k$ 色数图。

色数上界

对任意的无环图 $G$，均有：

$$\chi (G)\le \mathrm{\Delta }+1$$

任意一个顶点度数至多为 $\mathrm{\Delta }$, 因此，正常着色过程中，其邻点最多用去 $\mathrm{\Delta }$ 种颜色，所以，至少还有一种色可供该点正常着色使用。

---

证明 ：我们对顶点数作数学归纳证明。

当 $n=1$ 时，结论显然成立。

设对顶点数少于 $n$ 的图来说，定理结论成立。考虑一般的 $n$ 阶图 $G$，任取 $v\in V(G)$，令 $G_1=G-v$， 由归纳假设：

$$\chi (G_1)\le \mathrm{\Delta }(G_1)+1\le \mathrm{\Delta }(G)+1$$

设 $\pi$ 是 $G_1$ 的一种 $\mathrm{\Delta }(G_1)+1$正常点着色方案，因为 $v$ 的邻点在 $\pi$ 下至多用去 $\mathrm{\Delta }(G)$ 种色，所以给 $v$ 染上其邻点没有用过的色，就把 $\pi$ 扩充成了 $G$ 的 $\mathrm{\Delta }(G_1)+1$ 着色方案。

最大色数的正常着色算法

设 $G=(V,E)$，$V=\{v_1,v_2,\cdots ,v_n\}$，色集合 $C=\{1,2,\cdots ,\mathrm{\Delta }+1\}$，着色方案为 $\pi$.

• (1) 令 $\pi (v_1)=1$；
• (2) for i in 1..n 循环 $n-1$ 次：（若 $i=n$，则停止）
• 令：$C(v_{i+1})=\{\pi (v_j)|j\le i,v_j\text{adj}{v}_{i+1}\}$；
• 设 $k$ 为 $C-C(v_{i+1})$ 中的最小整数；
• 令 $\pi (v_{i+1})=k$；

Welsh-Powell 稍微对上面算法做了一个修改，着色时按所谓最大度优先策略，即使用上面算法时，$V=\{v_1,v_2,\cdots ,v_n\}$ 按顶点度数由大到小的次序着色。这样的着色方案起到了对上面算法的一个改进作用，有机会得到色数更小的结果。

布鲁克斯定理

给出了一些图的更小的上界

若 $G$ 是连通的单图，并且它既不是奇圈，又不是完全图，则：

$$\chi (G)\le \mathrm{\Delta }(G)$$

次大度

设 $G$ 是至少有一条边的简单图，定义：

$${\mathrm{\Delta }}_2(G)=\underset{u\in V(G)}{max}\underset{\begin{array}{r}v\in N(u)\\ d(v)\le d(u)\end{array}}{max}d(v)$$

其中 $N(u)$ 为 $G$ 中点 $u$ 的邻域。称 ${\mathrm{\Delta }}_2(G)$ 为 $G$ 的次大度。

布鲁斯克定理的改进

$$\chi (G)\le {\mathrm{\Delta }}_2(G)+1$$

设 $G$ 是非空简单图，若 $G$ 中最大度点互不邻接，则有：

$$\chi (G)\le \mathrm{\Delta }(G)$$

四色和五色定理

四色定理

五色定理

希伍德。

对任意简单图，都有：

$$\chi \le 5$$

该定理说明每个平面图是 5 可着色的。根据平面图和其对偶图的关系，该定理等价于每个平面图是 5 可顶点正常着色的。