# 边着色问题

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

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

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

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

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

$\chi'(G)$

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

$\chi'(G)\geq\Delta$

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

# 二部图

$\chi'(K_{m,n})=\Delta$

证明

假设：

$n\gt m$ $n > m$ ；
- 所以 $\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$ 着色方案，满足：

$\forall x_i y_j\in E(K_{m,n}),\ \ \pi(x_iy_j)=(i+j)(\bmod n)$

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

$(i+j)(\bmod n)=(i+k)(\bmod n)\\ \Downarrow\\ j=k$

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

同时 $\chi'(K_{m,n})\geq\Delta=n$ ，所以 $\chi'(K_{m,n})=n$ 。

# 偶图 (哥尼定理)

偶图 $G$ 的边色数：

$\chi'(G)=\Delta$

证明可利用数学归纳法

当 $m=1$ 时， $\Delta=1$ ，有 $\chi'(G)=\Delta=1$ 成立。

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

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

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

$\chi'(G_1)=\Delta(G_1)\leq\Delta(G)$

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

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

则在 $G_1+uv$ 中给 $uv$ 着色 $i$ , 而 $G$ 其它边按 $\pi$ 方案着色。这样得到 $G$ 的 $\Delta$ 着色方案，所以: $\chi'(G)=\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$ 的 $\Delta$ 正常边着色，即证明 $\chi'(G)=\Delta$ 。

# 一般简单图

# 引理

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

# 维津定理 (Vizing)

若图 $G$ 是简单图，则 $\chi'(G)=\Delta$ 或 $\chi'(G)=\Delta+1$ 。

只需要证明 $\chi'(G)≤\Delta+1$ 即可。对 $G$ 的边数 $m$ 作数学归纳证明。

当 $m=1$ 时， $\Delta=1$ , $\chi'(G)=1<Δ+1$ 。

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

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

$\chi'(G_1)≤\Delta(G_1)+1≤\Delta(G)+1$

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

# 充分条件 1

给出了 Vizing 定理结论中 $\chi'(G)=\Delta$ 情况的充分条件

设 $G$ 是单图且 $\Delta(G)>0$ 。若 $G$ 中只有一个最大度点或恰有两个相邻的最大度点，则:

$\chi'(G)=\Delta(G)$

# 充分条件 2

给出了 Vizing 定理结论中 $\chi'(G)=\Delta+1$ 情况的充分条件

设 $G$ 是单图。若点数 $n=2k+1$ 且边数 $m>k\Delta$ ，则:

$\chi'(G)=\Delta(G)+1$

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

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

# 充分条件 3

给出了 Vizing 定理结论中 $\chi'(G)=\Delta+1$ 情况的充分条件

设 $G$ 是奇数阶 $\Delta$ 正则单图，若 $\Delta>0$ ，则:

$\chi'(G)=\Delta(G)+1$

证明：

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

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

由定理 $\chi'(G)=\Delta(G)+1$ 。

# 无环有重边图

维津定理 (Vizing)

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

$\chi'(G)\leq\Delta(G)+\mu$

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

# 边着色的应用

# 排课表问题

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

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

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

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

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

# 比赛安排问题

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

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

# 顶点着色

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

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

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

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

$\chi(G)$

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

# 色数上界

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

$\chi(G)\leq\Delta+1$

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

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

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

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

$\chi(G_1)\leq\Delta(G_1)+1\leq\Delta(G)+1$

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

# 最大色数的正常着色算法

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

(1) 令 $\pi(v_1)=1$ ；
(2) for i in 1..n 循环 $n-1$ $n - 1$ 次：（若 $i=n$ $i = n$ ，则停止）
- 令： $C(v_{i+1})=\{\pi(v_j)|j≤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)\leq\Delta(G)$

# 次大度

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

$\Delta_2(G)=\max_{u\in V(G)}\max_{\begin{aligned} v\in N(u)\\ d(v)\leq d(u) \end{aligned}} d(v)$

其中 $N(u)$ 为 $G$ 中点 $u$ 的邻域。称 $\Delta_2(G)$ 为 $G$ 的次大度。

布鲁斯克定理的改进

$\chi(G)\leq\Delta_2(G)+1$

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