着色问题
边着色问题¶
图的边着色，本质上是对应实际问题中的“划分”问题或“分类” 问题。
对 \(G\) 的边进行着色，若相邻边着不同颜色，则称对 \(G\) 进行正常边着色；
在对 \(G\) 正常边着色时，着相同颜色的边集称为该正常边着色的一个色组；
如果能用 \(k\) 种颜色对图 \(G\) 进行正常边着色，称 \(G\) 是 \(k\) 边可着色的；
对 \(G\) 进行正常边着色需要的最少颜色数称为 \(G\) 的边色数，记为：
着色需要满足相邻边着不同色，所以很自然地有：(对于无环图)
也就是边色数以最大顶点度为下限。
二部图¶
证明
假设：
- \(n\gt 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\) 着色方案，满足：
对 \(K_{m,n}\) 中任意两条邻接边 \(x_iy_j\) 和 \(x_iy_k\) ，若二者在 \(\pi\) 中着色相同，即 \(\pi(x_iy_j)=\pi(x_iy_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\) 的边色数：
证明可利用数学归纳法
当 \(m=1\) 时，\(\Delta=1\)，有 \(\chi'(G)=\Delta=1\) 成立。
设对于小于 \(m\) 条边的偶图来说命题成立。
设 \(G\) 是具有 \(m\) 条边的偶图。
取 \(uv\in G\) , 考虑 \(G_1=G-uv\), 由归纳假设有:
这说明， \(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\). 由归纳假设有:
于是，存在 \(G_1\) 的 \(\Delta(G)+1\) 正常边作色 \(\pi\)。显然 \(G\) 的每个顶点都至少缺少一种颜色。根据引理知 \(G+xy\) 是 \(\Delta(G) +1\) 可着色的。即证明: \(\chi'(G) ≤ \Delta(G)+1\)。
充分条件 1¶
::: primary 给出了 Vizing 定理结论中 \(\chi'(G)=\Delta\) 情况的充分条件 设 \(G\) 是单图且 \(\Delta(G)>0\)。若 \(G\) 中只有一个最大度点或恰有两个相邻的最大度点，则:
充分条件 2¶
::: primary 给出了 Vizing 定理结论中 \(\chi'(G)=\Delta+1\) 情况的充分条件 设 \(G\) 是单图。若点数 \(n=2k+1\) 且边数 \(m>k\Delta\)，则:
证明可利用反证法，若不然，由维津定理，\(\chi'(G)=\Delta(G)\)。
设 \(\pi\) 是 \(G\) 的 \(\Delta(G)\) 正常边着色方案，对于 \(G\) 的每个色组来说，包含的边数至多 \(\frac{n-1}{2}=k\)。这样：\(m(G)≤\Delta k\)，与条件矛盾。
充分条件 3¶
::: primary 给出了 Vizing 定理结论中 \(\chi'(G)=\Delta+1\) 情况的充分条件 设 \(G\) 是奇数阶 \(\Delta\) 正则单图，若 \(\Delta>0\)，则:
证明：
设 \(n=2k+1\)，因 \(G\) 是 \(\Delta\) 正则单图，且 \(\Delta>0\)，所以：
由定理 \(\chi'(G)=\Delta(G)+1\)。
无环有重边图¶
维津定理(Vizing)
设无环图 \(G\) 中边的最大重数为 \(\mu\)，则:
其中 \(\leq\) 边界是紧的，也就是等号是可以相等的。
边着色的应用¶
排课表问题¶
\(X,Y\) 分别表示教师、教学班的集合：
\(x_i\) 与 \(y_j\) 间连 \(p_{ij}\) 条边，得二部图 \(G=(X,Y)\)。
求最少排多少节课的问题，每节课可以有多个教学班同时上课，转化为如何在 \(G\) 中将边集 \(E\) 划分为互不相交的 \(p\) 个匹配，且使得 \(p\) 最小
如果每个匹配中的边用同一种颜色着色，不同匹配中的边不同颜色，则问题转化为在 \(G\) 中给每条边着色，相邻边着不同色，至少需要的颜色数
比赛安排问题¶
玩家为顶点，2 个玩家间进行一次比赛为一条边，求最少安排多少场比赛，每场比赛可以有多对玩家同时比赛。
Abstract
基于圈的边着色问题和顶点着色问题是完全等价的，因为边和点可互换。
顶点着色¶
对图 \(G\) 的每个顶点着色，使得相邻顶点着不同颜色，称为对 \(G\) 的正常顶点着色；
如果用 \(k\) 种颜色可以对 \(G\) 进行正常点着色，称 \(G\) 是 \(k\) 可着色的；
着同一种颜色的顶点集合称为一个色组，它们彼此互不相邻，所有又称为点独立集；
图 \(G\) 正常顶点着色需要的最少颜色数，称为图 \(G\) 的点色数，简称色数，记为：
色数为 \(k\) 的图称为 \(k\) 色数图。
色数上界¶
对任意的无环图 \(G\)，均有：
任意一个顶点度数至多为 \(\Delta\), 因此，正常着色过程中，其邻点最多用去 \(\Delta\) 种颜色，所以，至少还有一种色可供该点正常着色使用。
证明 ：我们对顶点数作数学归纳证明。
当 \(n=1\) 时，结论显然成立。
设对顶点数少于 \(n\) 的图来说，定理结论成立。考虑一般的 \(n\) 阶图 \(G\)，任取 \(v\in V(G)\)，令 \(G_1=G-v\)， 由归纳假设：
设 \(\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\) 次：（若 \(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\) 是连通的单图，并且它既不是奇圈，又不是完全图，则：
次大度¶
设 \(G\) 是至少有一条边的简单图，定义：
其中 \(N(u)\) 为 \(G\) 中点 \(u\) 的邻域。称 \(\Delta_2(G)\) 为 \(G\) 的次大度。
布鲁斯克定理的改进
设 \(G\) 是非空简单图，若 \(G\) 中最大度点互不邻接，则有：
四色和五色定理¶
四色定理¶
五色定理¶
希伍德。
对任意简单图，都有：
该定理说明每个平面图是 5 可着色的。根据平面图和其对偶图的关系，该定理等价于每个平面图是 5 可顶点正常着色的。