返回：0100 离散数学课程总目录 · 上一章：0110 平面图 · 下一章：0112 支配、覆盖、独立与匹配

1、学习目标

本章对应刘田老师图着色部分，资料包括点着色、色多项式、平面图着色、面着色和边着色。核心目标是掌握色数、色多项式、四色问题、边色数这条线。

2、颜色标注

颜色 含义
粉色 必背结论
蓝色 概念名称
橙色 易错点
绿色 证明提示

3、点着色与色数

点着色：

1
给顶点染色，使相邻顶点颜色不同。

k-可着色表示可用不超过 k 种颜色完成点着色。色数：

1
chi(G)=使 G 可着色的最小颜色数。

典型结果：

1
2
3
4
5
6
chi(K_n)=n
chi(C_{2r})=2
chi(C_{2r+1})=3
树 T_n 的色数为 2（n>=2）
chi(W_n)=4, n 偶数
chi(W_n)=3, n 奇数

二部图判定：

1
G 是 2-可着色图 <=> G 是二部图 <=> G 不含奇圈。

色数上界：

1
chi(G) <= Delta(G)+1

Brooks 定理：

1
2
n>=3 的连通图 G，若 G 不是完全图也不是奇圈，
则 chi(G) <= Delta(G)。

Brooks 定理的例外就是完全图和奇圈。K_n 的色数比最大度多 1，奇圈的色数也比最大度多 1。

4、点着色判定流程

1
2
3
4
5
1. 先看是否有奇圈：有奇圈则 chi(G)>=3；无奇圈且非零图则 chi(G)=2。
2. 看是否含 K_r 子图：若含 K_r，则 chi(G)>=r。
3. 用 Delta(G)+1 或 Brooks 定理给上界。
4. 若上下界相等，直接得到 chi(G)。
5. 若上下界不等，尝试显式构造着色方案。

常见下界：

1
omega(G) <= chi(G)

其中 omega(G) 是最大完全子图阶数。

常见上界：

1
chi(G) <= Delta(G)+1

5、色多项式

色多项式 f(G,k) 表示用 k 种颜色给 G 正常点着色的方案数。

常用公式：

1
2
3
f(K_n,k)=k(k-1)...(k-n+1)
f(T_n,k)=k(k-1)^{n-1}
f(C_m,k)=(k-1)^m + (-1)^m(k-1)

删除-收缩公式：

1
若 e 不是环，则 f(G,k)=f(G-e,k)-f(G/e,k)

若图由树和圈拼接，常把色多项式拆成树的因子和圈的因子。

色多项式性质：

1
2
3
4
5
6
f(G,k) 是 n 次多项式；
k^n 的系数为 1；
k^(n-1) 的系数为 -m；
常数项为 0；
最低非零项为 k^p，p 是连通分支数；
不同连通分支的色多项式相乘。

计算流程：

1
2
3
4
5
1. 先识别基本图：完全图、零图、树、圈。
2. 若图由割点或割集拼接，优先拆成小图相乘/相除。
3. 若无法直接拆分，选一条非环边 e，用删除-收缩公式。
4. 展开后检查次数、k^(n-1) 系数和常数项是否合理。
5. 色数 chi(G) 是使 f(G,k)>0 的最小正整数 k。

色多项式里的 k 是可用颜色总数，不是色数。f(G,chi(G)) 才是最少颜色下的正常着色方案数。

6、平面图着色、面着色与边着色

四色定理：

1
任意平面图都 4-可着色。

五色定理常用欧拉公式里的 delta(G)<=5 证明。

五色定理换色法的关键情形：

1
2
3
4
5
删去一个度数 <=5 的顶点 v。
先给 G-v 做 5-着色。
若 v 的邻点没用满 5 种颜色，直接给 v 剩余颜色。
若 5 个邻点用了 5 种颜色，考察只含两种颜色的导出子图。
利用 Jordan 定理，某一对颜色路径不连通，交换一个连通分支的两种颜色，再给 v 腾出颜色。

面着色：

1
给地图的面染色，使相邻面颜色不同。

平面图的面着色可转化为对偶图的点着色：

1
face-coloring(G) = vertex-coloring(G*)

边着色：

1
给边染色，使相邻边颜色不同。

边色数 chi'(G) 满足 Vizing 定理：

1
Delta(G) <= chi'(G) <= Delta(G)+1

边着色常见结论：

1
2
3
二部图：chi'(G)=Delta(G)
完全图 K_n，n 为偶数：chi'(K_n)=n-1
完全图 K_n，n 为奇数：chi'(K_n)=n

边着色应用模板：

1
2
3
4
1. 把“同一时间不能冲突”的对象建成边相邻关系。
2. 给边染色，颜色代表时间段/批次/课节。
3. 最少颜色数就是边色数 chi'(G)。
4. 若是二部图，直接用 chi'(G)=Delta(G)。

例如排课问题可建二部图：

1
2
3
4
教师集合 T 与班级集合 C 为两侧顶点；
教师给班级上一节课就连一条边；
边颜色表示课节。
最少课节数 = chi'(G)=Delta(G)。

7、习题与答案

习题 12.1

给定无向图 G，求色多项式、色数和指定代入值。

答案：

1
2
3
4
f(G,k)=k^5 - 5k^4 + 9k^3 - 7k^2 + 2k
chi(G)=3
f(G,3)=24
f(G,4)=216

习题 12.2

用割集分解定理求图 G 的色多项式。按定理 12.10 分解为 G_i 和 H_i 后代入公式，最终仍得：

1
f(G,k)=k^5 - 5k^4 + 9k^3 - 7k^2 + 2k

检查：

1
2
3
最高次为 5，说明图有 5 个顶点；
k^4 系数为 -5，说明图有 5 条边；
最低非零项是 k，说明图连通。

习题 12.3

G 由一棵 n(n>=2) 阶树和一个 m(m>=3) 阶圈组成，求 f(G,k)。

答案：

1
2
f(G,k)=f(T_n,k) f(C_m,k)
      =k(k-1)^{n-1}((k-1)^m+(-1)^m(k-1))

习题 12.11

若 G 是 3-正则哈密顿图，则：

1
chi'(G)=3

证明线索：3-正则给出 chi'(G)>=Delta=3。哈密顿回路是偶圈，可用两种颜色交替染色；不在回路上的边彼此不相邻，用第三种颜色即可。

关键点：3-正则图若有哈密顿回路 C，则每个顶点还剩 1 条不在 C 上的关联边；这些剩余边构成匹配，所以可以统一用第 3 种颜色。

习题 12.12

彼得森图：

1
2
chi'(G)=4
G 不是哈密顿图

理由：Vizing 定理给出 3<=chi'<=4，但 3 种颜色会在对称结构处造成冲突，所以边色数为 4。非哈密顿性可用删点后连通分支数超过删点数的哈密顿必要条件证明。

习题 12.13

连通简单平面图 G：

1
2
G 既 2-面可着色又 2-顶点可着色
<=> G 是不含奇圈的欧拉图。

证明线索：2-面可着色等价于平面图为欧拉图；2-顶点可着色等价于二部图，二部图等价于不含奇圈。

8、复盘清单

1
2
3
4
5
6
7
8
1. 会计算 K_n、树、圈的色多项式。
2. 会使用删除-收缩公式。
3. 会区分点着色、面着色、边着色。
4. 会用对偶图理解面着色。
5. 会用 Vizing 定理估计边色数。
6. 记住 Petersen 图边色数为 4 且非哈密顿。
7. 会用 Brooks 定理和奇圈/完全图例外判断色数。
8. 会把排课、调度问题转成二部图边着色。