图的着色

点着色

（讨论的是无自环无向图）

对无向图顶点着色，且相邻顶点不能同色。若 G 是 $k$- 可着色的，但不是 $(k-1)$- 可着色的，则称 k 是 G 的色数，记为 $\chi (G)$。

对任意图 G，有 $\chi (G)\le \mathrm{\Delta }(G)+1$，其中 $\mathrm{\Delta }(G)$ 为最大度。

Brooks 定理

设连通图不是完全图也不是奇圈，则 $\chi (G)\le \mathrm{\Delta }(G)$。

证明

证明

设 $|V(G)|=n$，考虑数学归纳法。

首先，$n\le 3$ 时，命题显然成立。

接下来，假设对于 $n-1$ 时的命题成立，下面我们要逐步强化命题。

不妨只考虑 $\mathrm{\Delta }(G)$- 正则图，因为对于非正则图来说，可以看作在正则图里删去一些边构成的，而这一过程并不会影响结论。

对于任意不是完全图也不是奇圈的正则图 G，任取其中一点 v，考虑子图 $H:=G-v$，由归纳假设知 $\chi (H)\le \mathrm{\Delta }(H)=\mathrm{\Delta }(G)$，接下来我们只需证明在 H 中插入 v 不会影响结论即可。

令 $\mathrm{\Delta }:=\mathrm{\Delta }(G)$，设 H 染的 $\mathrm{\Delta }$ 种颜色分别为 $c_1,c_2,\dots ,c_{\mathrm{\Delta }}$，v 的 $\mathrm{\Delta }$ 个邻接点为 $v_1,v_1,\dots ,v_{\mathrm{\Delta }}$。不妨假设 v 的这些邻接点颜色两两不同，否则命题得证。

接下来我们设所有在 H 中染成 $c_i$ 或 $c_j$ 的点以及它们之间的所有边构成子图 $H_{i,j}$。不妨假设任意 2 个不同的点 $v_i$，$v_j$ 一定在 $H_{i,j}$ 的同一个连通分量中，否则若在两个连通分量中的话，可以交换其中一个连通分量所有点的颜色，从而 $v_i$，$v_j$ 颜色相同。

这里的交换颜色指的是若图中只有两种颜色 a，b，那么把图中原来染成颜色 a 的点全部染成颜色 b，把图中原来染成颜色 b 的点全部染成颜色 a。

我们设上述连通分量为 $C_{i,j}$，那么 $C_{i,j}$ 一定只能是 $v_i$ 到 $v_j$ 的路。因为 $v_i$ 在 H 中的度为 $\mathrm{\Delta }-1$，所以 $v_i$ 在 H 中的邻接点颜色一定两两不同，否则可以给 $v_i$ 染别的颜色，从而和 v 的其他邻接点颜色重复，所以 $v_i$ 在 $C_{i,j}$ 中邻接点数量为 1，$v_j$ 同理。然后我们在 $C_{i,j}$ 中取一条 $v_i$ 到 $v_j$ 的路，令其为 P，若 $C_{i,j}\ne P$，那么我们沿着 P 顺次给路上的点染色，设遇到的第一个度数大于 2 的点为 u，注意到 u 的邻接点最多只用了 $\mathrm{\Delta }-2$ 种颜色，所以 u 可以重新染色，从而使 $v_i$，$v_j$ 不连通。

然后我们不难发现，对任意 3 个不同的点 $v_i$，$v_j$，$v_k$，$V(C_{i,j})\cap V(C_{j,k})=\{v_j\}$。

到这里我们对命题的强化工作就已经做完了。

接下来就很简单。首先，如果 v 的邻接点两两相邻，那么命题得证。不妨设 $v_1$，$v_2$ 不相邻，在 $C_{1,2}$ 中取 $v_1$ 的邻接点 w，交换 $C_{1,3}$ 中的颜色。得到的新图中，$w\in V(C_{1,2})\cap V(C_{2,3})$，矛盾。

至此命题证明完毕。

Welsh–Powell 算法

Welsh–Powell 算法是一种在 不限制最大着色数 时寻找着色方案的贪心算法。

对于无自环无向图 G，设 $V(G):=\{v_1,v_2,\dots ,v_n\}$ 满足。

$\mathrm{deg}(v_i)\ge \mathrm{deg}(v_{i+1}),\mathrm{\forall }1\le i\le n-1$

按 Welsh–Powell 算法着色后的颜色数至多为 $\underset{i=1}{\overset{n}{max}}min\{\mathrm{deg}(v_i)+1,i\}$, 该算法的时间复杂度为 $O(n\underset{i=1}{\overset{n}{max}}min\{\mathrm{deg}(v_i)+1,i\})=O(n^2)$。

过程

1. 将当前未着色的点按度数降序排列。
2. 将第一个点染成一个未被使用的颜色。
3. 顺次遍历接下来的点，若当前点和所有与第一个点颜色 相同 的点 不相邻，则将该点染成与第一个点相同的颜色。
4. 若仍有未着色的点，则回到步骤 1, 否则结束。

示例如下：

（由 Graph Editor 生成）

我们先对点按度数降序排序，得：

次序	1	2	3	4	5	6	7	8	9	10	11	12	13
点的编号	4	5	0	2	9	1	3	6	10	12	7	8	11
度数	5	5	4	4	4	3	3	3	3	3	2	2	1
$min\{\mathrm{deg}(v_i)+1,i\}$	1	2	3	4	5	4	4	4	4	4	3	3	2

所以 Welsh–Powell 算法着色后的颜色数最多为 5。

另外因为该图有子图 $C_3$, 所以色数一定大于等于 3。

• 第一次染色：

  

  染 4 9 3 11 号点。 - 第二次染色：

  

  染 5 2 6 7 8 号点。 - 第三次染色：

  

  染 0 1 10 12 号点。

证明

证明

对于无自环无向图 G，设 $V(G):=\{v_1,v_2,\dots ,v_n\}$ 满足

$\mathrm{deg}(v_i)\ge \mathrm{deg}(v_{i+1}),\mathrm{\forall }1\le i\le n-1$

令 $V_0=\varnothing$, 我们取 $V(G)\setminus \bigcup _{i=0}^{m-1}{V}_i$ 中的子集 $V_m$, 其中的元素满足

1. $v_{k_m}\in V_m$, 其中 $k_m=min\{k:v_k\notin \bigcup _{i=0}^{m-1}{V}_i\}$

2. 若

   $\{v_{i_{m,1}},v_{i_{m,2}},\dots ,v_{i_{m,l_m}}\}\subset V_m,i_{m,1}<i_{m,2}<\cdots <i_{m,l_m}$

   则 $v_j\in V_m$ 当且仅当

   1. $j>i_{m,l_m}$
   2. $v_j$ 与 $v_{i_{m,1}},v_{i_{m,2}},\dots ,v_{i_{m,l_m}}$ 均不相邻

显然若将 $V_i$ 中的点染成第 i 种颜色，则该染色方案即为 Welsh–Powell 算法给出的方案，显然有

• $V_1\ne \varnothing$
• $V_i\cap V_j=\varnothing ⟺i\ne j$
• $\mathrm{\exists }\alpha (G)\in {\mathbb{N}}^{\ast },\mathrm{\forall }i>\alpha (G),s.t.V_i=\varnothing$

我们只需要证明：

$\bigcup _{i=1}^{\alpha (G)}{V}_i=V(G)$

其中

$\chi (G)\le \alpha (G)\le \underset{i=1}{\overset{n}{max}}min\{\mathrm{deg}(v_i)+1,i\}$

上式左边的不等号显然成立，我们考虑右边。

首先我们不难得出：

若 $v\notin \bigcup _{i=1}^m{V}_i$，则 v 与 $V_1,V_2,\dots ,V_m$ 中分别至少有一个点相邻，从而有 $\mathrm{deg}(v)\ge m$

进而

$v_j\in \bigcup _{i=1}^{\mathrm{deg}(v_j)+1}{V}_i$

另一方面，基于序列 $\{V_i\}$ 的构造方法，我们不难发现

$v_j\in \bigcup _{i=1}^j{V}_i$

两式结合即得证。

边着色

对无向图的边着色，要求相邻的边涂不同种颜色。若 G 是 k- 边可着色的，但不是 $(k-1)$- 边可着色的，则称 k 是 G 的边色数，记为 ${\chi }^{\prime }(G)$。

Vizing 定理

设 G 是简单图，则 $\mathrm{\Delta }(G)\le {\chi }^{\prime }(G)\le \mathrm{\Delta }(G)+1$

若 G 是二部图，则 ${\chi }^{\prime }(G)=\mathrm{\Delta }(G)$

当 $n$ 为奇数（$n\ne 1$）时，${\chi }^{\prime }(K_n)=n$; 当 $n$ 为偶数时，${\chi }^{\prime }(K_n)=n-1$

二分图 Vizing 定理的构造性证明

证明

按照顺序在二分图中加边。

我们在尝试加入边 $(x,y)$ 的时候，我们尝试寻找对于 $x$ 和 $y$ 的编号最小的尚未被使用过的颜色，假设分别为 $l_x$ 和 $l_y$。

如果 $l_x=l_y$ 此时我们可以直接将这条边的颜色设置为 $l_x$。

否则假设 $l_x

---

本页面最近更新：2024/3/27 06:46:12，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：Tiphereth-A, zhouyuyang2002, Chrogeek, CoderOJ, Enter-tainer, iamtwz, ImpleLee, Ir1d, lyccrius, ouuan
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用