第七章 图的着色

7.1 边着色

现实生活中很多问题, 可以模型为所谓的图(边)着色问题来处理. 例如排课表问题, 光纤网络中的频率分配,寄存器资源分配, 任务指派, 会期安排问题等.

排课表问题: 设有 $m$ 位教师, $n$ 个班级, 其中教师 $xi$ 要给班级 $y_j$ 上 $p_{ij}$ 节课. 求如何在最少节次排完所有课. 建模: 令 $X=\{x_1,x_2,\dots ,x_m\},Y=\{y_1,y_2,\dots ,y_n\}$, $x_i$ 与 $y_j$ 间连 $p_{ij}$ 条边, 得二部图 $G=(X,Y)$. 于是, 问题转化为如何在 $G$ 中将边集 $E$ 划分为互不相交的 $p$ 个匹配, 且使得 $p$ 最小.

如果每个匹配中的边用同一种颜色染色, 不同匹配中的边用不同颜色染色, 则问题转化为在 $G$ 中给每条边染色, 相邻边染不同色, 至少需要的颜色数. 这就需要我们研究图着色问题.

相关概念

边着色

设 $G$ 是图, 对 $G$ 的边进行染色, 若相邻边染不同颜色, 则称对 $G$ 进行正常边着色(proper edge-coloring).

• 注: 正常边着色图不能有自环.

如果能用 $k$ 种颜色对图 $G$ 进行正常边着色, 称 $G$ 是 $k$ 边可着色的 ($k$-colorable).

★边色数

设 $G$ 是图, 对 $G$ 进行正常边着色需要的最少颜色数, 称为 $G$ 的边色数 (chromatic index), 记为: ${\chi }^{\prime }(G)$

• 注: 对图的正常边着色, 实际上是对 $G$ 的边集合的一种划分, 使得每个划分块是 $G$ 的一个边独立集; 图的边色数对应的是图的边独立集最小划分数. 因此, 图的边着色, 本质上是对应实际问题中的“划分”问题或“分类”问题.

色组 (类)

在对 $G$ 正常边着色时, 着相同颜色的边集称为该正常着色的一个色组 (类).

二部图的边色数

★定理: 完全二部图的边色数等于最大度

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

证明: 设 $X=\{x_0,x_1,...,x_{m-1}\},Y=\{y_0,y_1,...,y_{n-1}\}$

又设 $∆=n$, 即有 $m\le n$. 设颜色的集合为 $\{0,1,2,\dots ,n-1\}$, $\pi$ 是 $K_{m,n}$ 的一种 $n$ 着色方案, 满足

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

我们证明: 上面的着色是正常边着色.

对 $K_{m,n}$ 中任意的两条邻接边 $x_i{y}_j$ 和 $x_i{y}_k$. 若 $\pi (x_i{y}_j)=\pi (x_i{y}_k)$,​ 则: $i+j(\mathrm{m}\mathrm{o}\mathrm{d}n)=i+k(\mathrm{m}\mathrm{o}\mathrm{d}n)$, 得到 $j=k$, 矛盾！

所以, 上面着色是正常着色. 所以: ${\chi }^{\prime }(K_{m,n})\le n$.

又显然 ${\chi }^{\prime }(K_{m,n})\ge \Delta =n$, 所以, ${\chi }^{\prime }(K_{m,n})=\Delta$.

例

用最少的颜色数对 $K_{3,4}$ 正常边着色.

解: 用四种颜色着色:

$$\pi (x_i{y}_j)=(i+j)(\mathrm{m}\mathrm{o}\mathrm{d}4)$$

缺某色

设 $\pi$ 是 $G$ 的一种正常边着色. 若点 $u$ 关联边的着色没有用到颜色 $i$, 则称 $u$ 缺 $i$ 色 (color i missing on u).

★定理: 二部图的边色数等于最大度

(König, 1916) 若 $G$ 是二部图, 则 ${\chi }^{\prime }(G)=\Delta$.

证明: 我们对 $G$ 的边数 $m$ 作归纳.

当 $m=1$ 时, $\Delta =1$, 有 ${\chi }^{\prime }(G)=\Delta =1$

设对于小于 $m$ 条边的二部图来说命题成立. 设 $G$ 是具有 $m$ 条边的二部图.

取 $uv\in E(G)$, 考虑 $G_1=G-uv$, 由归纳假设有: ${\chi }^{\prime }(G_1)=\Delta (G_1)\le \Delta (G)$. 这说明, $G_1$ 存在一种 $\Delta (G)$ 边着色方案 $\pi$. 对于该着色方案, 因为 $uv$ 未着色, 所以点 $u$ 与 $v$ 均至少缺少一种色.

情形 1: 如果 $u$ 与 $v$ 均缺同一种色 $i$, 则在 $G_1+uv$ 中给 $uv$ 着色 $i$, 而 $G_1$ 其它边, 按 $\pi$ 方案着色. 这样得到 $G$ 的 $\Delta$ 着色方案, 所以: ${\chi }^{\prime }(G)=\Delta$.

情形 2: 如果 $u$ 缺色 $i$, 而 $v$ 缺色 $j$, 但不缺色 $i$.
设 $H(i,j)$ 表示 $G_1$ 中由 $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$ 的正常边着色. 但交换着色后, $u$ 与 $v$ 均缺色 $i$, 于是由情形1, 可以得到 $G$ 的 $\Delta$ 正常边着色, 即证明: ${\chi }^{\prime }(G)=\Delta$.

注: 在一条路上进行色交换的思想是 Kempe 在尝试证明四色定理的时首创的. 虽然 Kempe 未能如愿证明四色定理 (证明有误), 但该方法是图论中非常有用的方法之一.

一般简单图的边色数

引理

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

★Vizing 定理

(Vizing[1964], Gupta[1966]) 若 $G$ 是简单图, 则:

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

证明: 只需要证明 ${\chi }^{\prime }(G)\le \Delta +1$ 即可.

对 $G$ 的边数 $m$ 作数学归纳证明.

当 $m=1$ 时, $\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 \Delta (G_1)+1\le \Delta (G)+1$. 于是, 存在 $G_1$ 的 $\Delta (G)+1$ 正常边作色 $\pi$.

显然 $G_1$ 的每个顶点都至少缺少一种颜色. 根据引理知 $G_1+xy$ 是 $\Delta (G)+1$ 可着色的. 即证明: ${\chi }^{\prime }(G)\le \Delta (G)+1$.

第一类图, 第二类图

将 ${\chi }^{\prime }(G)=\Delta (G)$ 的简单图称为第一类图 (class one);

将 ${\chi }^{\prime }(G)=\Delta (G)+1$ 的简单图称为第二类图 (class two).

意外的是, 确定一般图是否第一类的问题是 NP-完全的. 甚至对 3 正则图, 边色数的问题都是 NP-完全的.

Erdos 和 Wilson 用随机方法证明几乎所有的图都是第一类的.

三类特殊简单图的边色数

★定理1

设 $G$ 是简单图且 $\Delta (G)>0$. 若 $G$ 中只有一个最大度点或恰有两个相邻的最大度点, 则: ${\chi }^{\prime }(G)=\Delta (G)$.

证明:

(1) 若简单图 $G$ 恰有一个最大度点 $u$, 取 $u$ 的一个邻点 $v$, 作 $G_1=G-uv$.
那么, $\Delta (G_1)\le \Delta (G)-1$.
由 Vizing 定理: ${\chi }^{\prime }(G_1)\le (\Delta (G)-1)+1=\Delta (G)$.
于是 $G_1$ 是可 $\Delta (G)$ 正常边着色的, 因为 $G_1$ 的每个顶点都至少缺少一种颜色, 所以由引理: $G_1+uv=G$ 是可 $\Delta (G)$ 正常边着色的, 即: ${\chi }^{\prime }(G)=\Delta (G)$.

(2) 若简单图 $G$ 恰有 $2$ 个邻接的最大度点 $u$ 与 $v$. 设 $G_1=G-uv$.
那么, $\Delta (G_1)=\Delta (G)-1$.
由 Vizing 定理: ${\chi }^{\prime }(G_1)\le (\Delta (G)-1)+1=\Delta (G)$.
于是 $G_1$ 是可 $\Delta (G)$ 正常边着色的, 因为 $G_1$ 的每个顶点都至少缺少一种颜色, 所以由引理: $G_1+uv=G$ 是可 $\Delta (G)$ 正常边着色的, 即: ${\chi }^{\prime }(G)=\Delta (G)$

例

确定下图的边色数.

解: 由上述定理知道:

$\Delta (G_1)=4$, 恰有一个最大度点, 故 ${\chi }^{\prime }(G_1)=4$.

$\Delta (G_2)=5$, 恰有一个最大度点, 故 ${\chi }^{\prime }(G_2)=5$.

$\Delta (G_3)=4$, 恰有 $2$ 个邻接的最大度点, 故 ${\chi }^{\prime }(G_3)=4$.

★定理2

设 $G$ 是简单图. 若顶点数 $n=2k+1$ 且边数 $m>k\Delta$, 则: ${\chi }^{\prime }(G)=\Delta (G)+1$.

证明: 若不然, 由 Vizing 定理, ${\chi }^{\prime }(G)=\Delta (G)$.

设 $\pi$ 是 $G$ 的 $\Delta (G)$ 正常边着色方案, 对于 $G$ 的每个色类来说, 包含的边数至多 $(n-1)/2=k$. 这样: $m(G)\le \Delta k$, 与条件矛盾.

例

确定下图的边色数.

解: 由上述定理, 图 $G$ 顶点数 $n=5$, $k=2$, $\Delta (G)=4$, 边数 $m=9>k\Delta =8$, 故 ${\chi }^{\prime }(G)=\Delta (G)+1=5$.

★定理3

设 $G$ 是奇数阶 $\Delta$ 正则简单图, 若 $\Delta >0$, 则: ${\chi }^{\prime }(G)=\Delta (G)+1$.

证明: 设 $n=2k+1$. 因 $G$ 是 $\Delta$ 正则简单图, 且 $\Delta >0$, 所以:

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

由定理2: ${\chi }^{\prime }(G)=\Delta (G)+1$.

例

设 $n=2k+1,k>0$. 求 ${\chi }^{\prime }(C_n),{\chi }^{\prime }(K_n)$.

解: 由上述定理知:

${\chi }^{\prime }(C_n)=2+1=3$.

${\chi }^{\prime }(K_n)=(n-1)+1=n$.

练习: 设 $n=2k,k>0$. 求 ${\chi }^{\prime }(C_n),{\chi }^{\prime }(K_n)$.

对于 $C_n$ 使用两种颜色交替着色即可, 故 ${\chi }^{\prime }(C_n)=2$.

${\chi }^{\prime }(K_n)=n-1$.

例

求出 Petersen 图的边色数.

解: 一方面, Petersen图中去掉任意一个 $1$ 因子后, 剩下两个 $5$ 长圈, 所以, 不能 $1$ 因子分解. 故: ${\chi }^{\prime }(G)\ge 4$.
另一方面: 通过验证, $G$ 可以 $4$ 正常着色. 所以: ${\chi }^{\prime }(G)=4$.

注: 事实上, $k$-正则图是第一类的⟺可 $1$ 因子分解. 故判定一般 $k$ 正则图 (非二部, $k\ge 3$) 是否可 $1$ 因子分解也是 NP-完全的.

例

求证: 每个哈密尔顿 $3$ 正则图都有泰特着色. $3$ 正则图的正常 $3$ 边着色称为泰特 (Tait) 着色.

证明: 设 $G$ 是 $3$ 正则 H 图, $C$ 是 $G$ 的一个 H 圈, 则 $C$ 是二部圈, 所以 $C$ 是 $2$ 可正常边着色的. 因 $G-C$ 是 $G$ 的一个 $1$ 因子, 所以, 可 $1$ 正常边着色. 因此, $G$ 是可以 $3$ 边正常着色的, 即 $G$ 有泰特着色 (事实上, 第五章中已证明该图可 $1$-因子分解).

注: Tait提出Tait着色是为了证明“四色定理”. 因为如果证明了每个3连通3正则平面图的边色数是3, 那么“四色定理”就得到证明. Tait(1880)认为: 每个3连通3正则平面图是H图, 所以由上面例7, Tait深信他已经证明了“四色定理”. 非常遗憾, Tutte 1946年通过构图方式否定了每个3连通3正则平面图是H图的断言.

非简单图的边色数

Vizing 定理 (非简单图)

设无环图 $G$ 中边的最大重数为 $\mu$, 则, ${\chi }^{\prime }(G)\le \Delta +\mu$.

例如, 下图是一个边色数达到 $\Delta +\mu$ 的图, 其中 $\Delta =4,\mu =2$.

★边着色的应用

边着色对应的实际问题就是图的匹配分解问题. 边色数对应的是最小匹配分解问题. 所以, 生活中的许多问题都可模型为边着色问题来解决.

排课表问题

在一个学校中, 有 $7$ 个教师 $12$ 个班级. 在每周 $5$ 天教学日条件下, 教课的要求由如下矩阵给出:

$$P=\left(\begin{array}{cccccccccccc}3& 2& 3& 3& 3& 3& 3& 3& 3& 3& 3& 3\\ 1& 3& 6& 0& 4& 2& 5& 1& 3& 3& 0& 4\\ 5& 0& 5& 5& 0& 0& 5& 0& 5& 0& 5& 5\\ 2& 4& 2& 4& 2& 4& 2& 4& 2& 4& 2& 3\\ 3& 5& 2& 2& 0& 3& 1& 4& 4& 3& 2& 5\\ 5& 5& 0& 0& 5& 5& 0& 5& 0& 5& 5& 0\\ 0& 3& 4& 3& 4& 3& 4& 3& 4& 3& 3& 0\end{array}\right)$$

其中, $p_{ij}$ 表示 $x_i$ 必须教 $y_j$ 班的节数. 求: 一天分成几节课, 才能满足所提出的要求？

解: 问题可模型为一个二部图. 一节课对应边正常着色的一个色组. 由于 $G$ 是二部图, 所以边色数为 $G$ 的最大度 $35$. 这样, 最少总课时为 $35$ 节课. 平均每天要安排 $7$ 节课.

★比赛安排问题

Alvin (A) 曾邀请 3 对夫妇到他的避暑别墅住一个星期. 他们是: Bob 和 Carrie , David 和 Edith, Frank 和 Gena. 由于这 6 人都喜欢网球运动, 所以他们决定进行网球比赛. 6 位客人的每一位都要和其配偶之外的每位客人比赛. 另外, Alvin 将分别和 David, Edith, Frank, Gena 进行一场比赛. 若没有人在同一天进行 2 场比赛, 则要在最少天数完成比赛, 如何安排?

解: 用点表示参赛人, 两点连线当且仅当两人有比赛. 这样得到比赛状态图.

问题对应于求状态图的一种最优边着色(用最少色数进行正常边着色).

由于 $n=2\times 3+1$, 所以 $k=3$ (每天最多有3场比赛). 而$\Delta =5,m=16>3\times 5=k\Delta$, 所以由定理2知: ${\chi }^{\prime }(G)=6$.

最优着色为:

7.2 顶点着色

相关概念

点着色

设 $G$ 是一个图, 对 $G$ 的每个顶点着色, 使得相邻顶点着不同颜色, 称为对 $G$ 的正常点着色 (proper coloring).

如果用 $k$ 种颜色可以对 $G$ 进行正常点着色, 称 $G$ 可 $k$ 正常点着色 (proper $k$-coloring).

★点色数

对图 $G$ 正常顶点着色需要的最少颜色数, 称为图 $G$ 的点色数 (chromatic number). 图 $G$ 的点色数用 $\chi (G)$ 表示.

例

说明下图的点色数是4.

解: 一方面, 由图的结构特征容易知道 $\chi (G)\ge 4$, 因为 LA 与其余 5 个点相连, 不能和其余 5 个点着相同色, 其余 5 个点构成一个 5 长圈, 至少需要 3 个颜色.

另一方面, 通过具体着色, 用 4 种颜色可以得到该图的一种正常点着色, 则: $\chi (G)\le 4$.

所以, $\chi (G)=4$.

色组

注: 对图的正常顶点着色, 带来的是图的顶点集合的一种划分方式. 所以, 对应的实际问题也是分类问题.

属于同一种颜色的顶点集合称为一个色组, 它们彼此不相邻接, 所以又称为点独立集.

色数为 $k$ 的图称为 $k$ 色的 ($k$-chromatic).

图的点色数的几个结论

$K_n$ 的点色数

显然 $\chi (G)\le n$, 且仅对 $K_n$ 有 $\chi (G)=cl(K_n)=n$. 对一般图 $\chi (G)\le n$ 未考虑到图的任何结构信息.

★定理

对任意的图 $G$, 有: $\chi (G)\le \Delta (G)+1$.

分析: 事实上, 定理结论容易想到, 因为任意一个顶点度数至多为 $\Delta$. 因此, 正常着色过程中, 其邻点最多用去 $\Delta$ 种颜色, 所以, 至少还有一种色可供该点正常着色使用.

证明: 我们对顶点数作数学归纳证明.

当 $n=1$ 时, 结论显然成立.

设对顶点数少于 $n$ 的图来说, 定理结论成立. 考虑一般的 $n$ 阶图 $G$.

任取 $v\in V(G)$, 令 $G_1=G-v$, 由归纳假设: $\chi (G_1)\le \Delta (G_1)+1\le \Delta (G)+1$.

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

$\Delta +1$ 正常点着色算法

对于 $G$ 来说, 可以给出其 $\Delta (G)+1$ 正常点着色算法.

$G$ 的 $\Delta (G)+1$ 正常点着色算法 (Greedy strategy)

设 $G=(V,E),V=\{v_1,v_2,\dots ,v_n\}$, 色集合 $C=\{1,2,\dots ,\Delta +1\}$, 着色方案为 $\pi$.
(1) 令 $\pi (v_1)=1,i=1$;
(2) 若 $i=n$, 则停止;
否则若 $k$ 为与 $v_{i+1}$ 相邻的顶点里未使用的标号最小的色号, 且令 $\pi (v_{i+1})=k$.
(3) 令 $i=i+1$, 转(2).

例

给出下图的 $\Delta +1$ 正常点着色.

解: 颜色集 $C=\{1,2,3,4,5\}$

(1) $\pi (v_1)=1$,
(2) $k=2,\pi (v_2)=2$,
(3) $k=3,\pi (v_3)=3$,
(4) $k=1,\pi (v_4)=1$,
(5) $k=2,\pi (v_5)=2$,
(6) $k=4,\pi (v_6)=4$.

注

(1) 不能通过上面算法求出色数. 例如, 根据上面算法, 我们求出了一个 $4$ 色方案, 但 $G$ 是 $3$ 色图:

(2) 该算法求出的颜色数依赖于顶点的编号(亦即顶点编号不同, 求出的颜色数可能不同)

(3) 一种策略就是对每一种顺序的顶点编号, 均用该算法得到颜色数, 最后再比较求出最小的颜色数就是点色数. 但要对 $n!$ 种顶点都计算, 显然非多项式时间!

(4) Welsh—Powell (1967) 对上面算法做了一个修改, 着色时按所谓最大度优先策略(即考虑图的结构), 即用上面算法时, 按顶点度数由大到小的次序着色. 这样的着色方案是对上面算法的一个改进(也仅仅是一个改进, 没有彻底解决点色数的问题), 得到 $\le {\max }_i\min \{d_i,i-1\},1\le i\le n$.

Petersen 图的点色数

试求 Petersen 图的点色数.

解: 找到 Petersen 图 $G$ 的一个 $4$ 点独立集, 其余 $6$ 个点的导出子图是 $3K_2$, $\chi (G)\ge 3$.

又给出一个 $3$ 着色方案, 得到 $\chi (G)\le 3$.

综上, $\chi (G)=3$.

★Brooks 定理

对于简单图 $G$ 来说, 数学家 Brooks 给出了一个对定理的改进. 这就是下面著名的 Brooks 定理.

(Brooks, 1941) 若 $G$ 是连通的简单图, 并且它既不是奇圈, 又不是完全图, 则: $\chi (G)\le \Delta (G)$.

Lovász 在 1975 年给出了如下漂亮证明.

证明: 略.

注:

(1) 对点色数, Brooks 定理可以得到其上界为 $\Delta (G)$, 并可应用贪婪算法得到 $\Delta (G)+1$ 种颜色的染色方式.

(2) 对一般图来说, 判定其是否是 $3$ 可着色的问题是 NP-完全的. 求一般图的色数问题是 NP-困难的. 这也就是 Brooks 定理仅能给出上界的原因.

关于色数的一个猜想

一般来说, 以下情况成立:

$$\chi (G\times H)\le \min \{\chi (G),\chi (H)\}$$

1966 年, Stephen T.Hedetniemi 进一步推测 $\chi (G\times H)=\min \{\chi (G),\chi (H)\}$.

2019 年, Yaroslav Shitov 证明了 $\chi (G\times H)$ 可以小于 $\min \{\chi (G),\chi (H)\}$.

四色与五色定理

四色定理

1852 年, 刚毕业于 University College London 的 Francis Guthrie (1831-99) 发现: 给一张英国地图 (平面的) 正常着色, 仅需要 4 种颜色. 这就是著名的 4 色问题.

20 世纪 70 年代, Haken 和他的学生 Appel 着力用计算机方法证明 4 色定理, 借助于 Appel 在编程方面的深厚功底. 他们于 1976 年 6 月终于成功解决了寻找不可约构形集合中的元素, 宣告 4 色定理的成功证明.

五色定理 (Heawood)

每个平面图是 $5$ 可着色的.

根据平面图和其对偶图的关系, 上面定理等价于每个平面图是 5 可顶点正常着色的.

证明: 我们对图的顶点作归纳.

当 $n=1$ 时, 结论显然. 假设 $n=k$ 时结论成立. 考虑 $n=k+1$ 的连通平面图 $G$.

因 $G$ 是连通平面图, 所以 $\delta (G)\le 5$. 设 $d(u)=\delta (G)\le 5$.

令 $G_1=G–u$. 由归纳假设, $G_1$ 是 $5$ 可顶点正常着色的. 设 $\pi$ 是 $G_1$ 的 $5$ 着色方案.

(1) 如果 $d(u)=\delta (G)<5$, 显然 $\pi$ 可以扩充为 $G$ 的 $5$ 正常顶点着色;

(2) 如果 $d(u)=\delta (G)=5$, 分两种情况讨论.

情形 1: 在 $\pi$ 下, 如果 $u$ 的邻接点中, 至少有两个顶点着相同颜色, 则容易知道, $\pi$ 可以扩充为 $G$ 的 $5$ 正常顶点着色;

情形 2: 在 $\pi$ 下, 设 $u$ 的邻接点中, $5$ 个顶点着了 $5$ 种不同颜色.

不失一般性, 设 $\pi (x_i)=i(1\le i\le 5)$. 设 $H(i,j)$ 表示着 $i$ 和 $j$ 色的点在 $G_1$ 中的点导出子图.

如果 $x_1$ 与 $x_3$ 属于 $H(1,3)$ 的不同分支. 则通过交换含 $x_1$ 的分支中的着色顺序, 可得到 $G_1$ 的新正常点着色方案, 使 $x_1$ 与 $x_3$ 着同色, 于是由情形 1, 可以得到 $G$ 的 $5$ 正常顶点着色方案;

设 $x_1$ 与 $x_3$ 属于 $H(1,3)$ 的相同分支.

在上面假设下, $x_2$ 与 $x_4$ 必属于 $H(2,4)$ 的不同分支. 否则, 将会得到 $H(1,3)$ 与 $H(2,4)$ 的交叉点. 因此, $\pi$ 可以扩充为 $G$ 的 $5$ 正常顶点着色.

★顶点着色的应用

图的正常顶点着色对应的实际问题是“划分”问题.

★课程安排问题

某大学数学系要为这个夏季安排课程表. 所要开设的课程为: 图论(GT), 统计学(S), 线性代数(LA), 高等微积分(AC), 几何学(G), 和近世代数(MA). 现有10名学生(如下所示)需要选修这些课程. 根据这些信息, 确定开设这些课程所需要的最少时间段数, 使得学生选课不会发生冲突. (学生用Ai表示)

A1: LA, S;
A2: MA, LA, G;
A3: MA, G, LA;
A4: G, LA, AC ;
A5: AC, LA, S;
A6: G, AC;
A7: GT, MA, LA;
A8: LA, GT, S;
A9: AC, S, LA;
A10: GT, S.

解: 把课程模型为图G的顶点, 两顶点连线当且仅当有某个学生同时选了这两门课程.

如果我们用同一颜色给同一时段的(冲突的)课程顶点染色, 那么, 问题转化为在状态图中求对应于图的点色数及其着色方案.

(1) 求点色数

一方面, 因图中含有奇圈 (红色边), 所以, 点色数至少为 $3$. 又因为点 LA 与该圈上每一个点均邻接, 所以, 点色数至少为 $4$. 另一方面, 我们用 $4$ 种色实现了 $G$ 的正常点着色. 所以, 图的点色数为 $4$.

(2) 具体安排

★交通灯的相位设置问题

如图所示, 列出了繁华街道路口处的交通车道 L1, L2, …, L9. 在此路口处安置了交通灯. 当交通灯处于某个相位时, 亮绿灯的车道上的车辆就可以安全通过路口. 为了让所有的车辆都能安全通过路口(包括不同车辆驶入同一车道), 交通灯所需相位的最小数目是多少?

解: 车道模型为顶点, 两点连线当且仅当两个车道上的车不能同时安全地进入路口.

问题转化为求 $G$ 的点色数. 一方面, $G$ 中含有 $K_4$. 所以, 点色数至少为 $4$.

另一方面, 通过尝试, 用 $4$ 种色实现了正常点着色.

所以, 最小相位为 $4$.

7.3 〇与色数有关的几类图

临界图

(色) 临界图

若对图 $G$ 的任意真子图 $H$, 都有 $\chi (H)<\chi (G)$, 则称 $G$ 是 (色) 临界图 (color-critical).

$k$ 临界图

点色数为 $k$ 的临界图称为 $k$ 临界图 (k-critical graph).

定理 (Dirac, 1952)

临界图有如下性质:
(1) $k$ 色图均有 $k$ 临界子图;
(2) 每个临界图均为简单连通图;
(3) 若 $G$ 是 $k$ 临界图, 则 $\delta \ge k-1$.

证明:

(1) 是显然的. (注: 但是没有好的算法)

(2) 显然图无自环. 删掉平行边中的一条边并不影响原有的顶点正常着色, 所以每个临界图是简单图; 又因为删掉色数较小的分支, 剩下部分的图的色数和原图色数相等, 所以, 临界图必连通.

(3) 若不然, $\delta (G)<k-1$.
设 $d(v)=\delta$. 因为 $G$ 是 $k$ 临界图, 所以 $G-v$ 是 $k-1$ 可正常顶点着色的. 设 $\pi$ 是 $G-v$ 的 $k-1$ 正常顶点着色方案, 显然, 它可以扩充为 $G$ 的 $k-1$ 正常点着色方案. 这与 $G$ 是 $k$ 临界图相矛盾.

推论

每个 $k$ 色图至少有 $k$ 个度不小于 $k-1$ 的顶点.

证明: 因 $G$ 是 $k$ 色图, 所以, 它包含 $k$ 临界子图 $G_1$, 所以有: $\delta (G_1)\ge k-1$, 即 $G_1$ 中至少有 $k$ 个顶点, 其度数不小于 $k-1$. 所以, $G$ 中至少有 $k$ 个度不小于 $k-1$ 的顶点.

例

利用上面推论证明: 对任意图 $G$, 有: $\chi (G)\le \Delta (G)+1$.

证明: 设 $G$ 的点色数为 $\chi (G)$. 由推论, $G$ 中至少有 $\chi (G)$ 个顶点, 其度数不小于 $\chi (G)-1$.

所以, $\Delta (G)\ge \chi (G)-1$, 即: $\chi (G)\le \Delta (G)+1$.

例

求证: (Dirac, 1952) 临界图没有割点.

证明: 设 $G$ 是 $k$ 临界图. 如果 $G$ 有割点 $v$, 设 $G_1,G_2,\dots ,G_r$ 是 $G-v$ 的分支. 又设第 $i$ 个分支顶点集为 $V_i(1\le i\le r)$.

设 $H_i=G[V_i\cup v],(1\le i\le r)$. 则 $H_i$ 是 $k-1$ 可正常点着色的, 现对每个 $H_i$ 进行 $k-1$ 正常点着色, 且 $v$ 都分配同一种颜色, 那么, 将着色后的 $H_i$ 合在一起, 得到 $G$ 的 $k-1$ 正常点着色方案, 这与 $G$ 是 $k$ 色图矛盾. 所以临界图没有割点.

例

求证: 仅有的 $1$ 临界图是 $K_1$; 仅有的 $2$ 临界图是 $K_2$; 仅有的 $3$ 临界图是奇圈.

证明: 由于 $1$ 色图是空图, 所以 $1$ 临界图只能是 $K_1$; $2$ 色图是二部图, 所以, $2$ 临界图只能是 $K_2$; $3$ 色图必然含有奇圈, 而奇圈的色数是 $3$, 所以, $3$ 临界图只能是奇圈.

不含三角形的 $k$ 色图

不含三角形的 $k$ 色图

若图 $G$ 的点色数是 $k$, 且 $G$ 中不含有三角形, 称 $G$ 是一个不含三角形的 $k$ 色图 (triangle-free k-critical graph).

构造不含三角形的 $k$ 色图

1953年, Dirac 在 “$k$ 色图的构造” 一文中提出一个问题: 对于任意大的一个正整数 $k$, 是否存在一个图, 不包含三角形但色数是 $k$？上面问题分别由勃兰克.斯德卡兹 (1954), Mycielski (1955) 独立作出了回答.

Mycielski (1955) 给出了由一个不含三角形的 $k$ 色图 $G_k$ 构造一个不含三角形的 $k+1$ 色图 $G_{k+1}$ 的方法.

构造方法: 设 $G_k$ 的顶点是 $u_1,u_2,\dots ,u_n$, 添加点 $v_1,v_2,\dots v_n$ 和点 $v$. 将 $v_i$ 与 $u_i$ 的所有邻点及 $v$ 相连, $1\le i\le n$. 如此得到的图就是一个不含三角形的 $k+1$ 色图.

例

利用 Mycielski 方法构造一个不含三角形的 $4$ 色图.

解:

定理 (Mycielski)

对任意正整数 $k$, 存在不含三角形的 $k$ 色图.

注: 一般地有 $\chi (G)\ge cl(G)$. 其中 $cl(G)$ 是 $G$ 的最大团的阶数. 由此构造可以看出 $\chi (G)$ 可以远远大于 $cl(G)$.

7.4 〇完美图

相关概念

团

若简单图 $G$ 的一个顶点子集 $S$ 在 $G$ 中的导出子图是完全图, 则称 $S$ 是 $G$ 的一个团 (clique).

团数 $cl(G)$

简单图 $G$ 的最大团包含的顶点数称为 $G$ 的团数 (clique number), 记为 $cl(G)$, 即:

$$cl(G)=max\{|S||S\text{是}G\text{的团}\}$$

显然, 图 $G$ 的点色数与团数的关系为: $\chi (G)\ge cl(G)$.

完美图

设 $G$ 是一个图. 若对 $G$ 的每个点导出子图 $H$, 均有 $\chi (H)=cl(H)$, 则称 $G$ 为完美图 (perfect graph).

例如 $K_n$, 二部图都是完美图.

而不含三角形但含奇圈的图不是完美图. 因为不含三角形的但含奇圈的图的团数为 $2$, 但色数为 $3$.

对该问题的研究, 早在 1932 年 Konig 和 Gallai 就已经涉及, 但到了 1960 年, 完美图概念才被 Berge 正式提出.

点独立集

设 $G$ 是一个图. 由 $G$ 中若干互不邻接的顶点作成的子集称为 $G$ 的一个点独立集 (independence set)

独立数 $\alpha (G)$

$G$ 中含顶点数最多的点独立集称为 $G$ 的最大独立集, 其包含的顶点数称为独立数 (independence number), 记为 $\alpha (G)$.

关于独立数的完美图

注: 关于图的覆盖与图的点独立数之间的关系, Gallai 得到了一些很漂亮的结论.

完全数 $\theta (G)$

设 $S$ 是图 $G$ 的顶点集合的一个划分. 如果 $S$ 的每个子集在 $G$ 中的导出子图均是完全图, 称 $S$ 是 $G$ 的一个完全分类. $G$ 的最小完全分类所包含的元素个数称为 $G$ 的完全数, 记为 $\theta (G)$, 即:

$$\theta (G)=min\{|S||S为G的完全分类\}$$

注: $\alpha (G)\le \theta (G)$. 这是因为独立集中任意一点应该属于 $S$ 中的某个顶点子集, 同时, $S$ 中每个顶点子集最多包含独立集中的一个元素.

关于点独立集的完美图

若对 $G$ 中每个点导出子图 $H$, 都有 $\alpha (H)=\theta (H)$, 称 $G$ 是关于点独立集的完美图.

完美图定理

1960年, 数学家 Berge 猜想: 关于色数的完美图定义和关于独立集的完美图定义是等价的. 即下面著名的完美图定理.

$G$ 是关于色数的完美图当且仅当 $G$ 是关于独立集的完美图.

定理

由完美图定理, 可以得到如下定理:

$G$ 是完美图当且仅当其补图是完美图.

关于完美图的结构研究

强完美图定理

在关于完美图结构的问题上, Berge 提出了下面的强完美图猜想 (SPGC猜想, 1961)

图 $G$ 是完美的当且仅当 $G$ 和其补图均没有导出子图是长度至少为 $5$ 的奇圈.

注: 强完美图猜想在2002年由 Maria Chudnovsky, Neil Robertson, Paul Seymour, 和 Robin Thomas证明. "The strong perfect graph theorem", Annals of Mathematics, 164 (1):51–229

7.5 着色的计数与色多项式

色多项式

★色多项式 $P_k(G)$

George David Birkhoff (1884.3.21-1944.11.12, 1907年获芝加哥大学博士, 1925年任美国数学会主席) 为了尝试证明四色定理而定义了色多项式.

给定图 $G$ 和颜色数 $k\in N$, $P_k(G)$ 的值是对 $G$ 正常 $k$ 点着色的方式数, 即满足 $f:V(G)\to [k]$ 是正常点着色的所有映射的数目, 其中 $[k]=\{1,2,\cdots ,k\}$.

给一个点着不同的颜色, 则产生不同的染色方式.

可以证明: $P_k(G)$ 是 $k$ 的多项式, 称为图 $G$ 的色多项式 (chromatic polynomial).

色多项式的性质

由点色数 $\chi (G)$ 和色多项式 $P_k(G)$ 的定义可得:

• (1) 若 $k<\chi (G)$, 则 $P_k(G)=0$; $\chi (G)=\min \{k|P_k(G)\ge 1\}$.
• (2) 若 $G$ 为空图, 则 $P_k(G)=k^n$.
• (3) $P_k(K_n)=k(k-1)\cdots (k-n+1)$.

色多项式的两种求法

• 递推计数法
• 理想子图计数法

递推计数法

★定理

设 $G$ 为简单图, 则对任意 $e\in E(G)$ 有:

$$P_k(G)=P_k(G-e)-P_k(G\cdot e)$$

证明: 设 $e=uv$. 则对 $G-e$ 的着色方式数可以分为两部分:
(1) $u$ 与 $v$ 着不同颜色. 此时, 等于 $G$ 的着色方式数;
(2) $u$ 与 $v$ 着同色. 此时, 等于 $G\cdot e$ 的着色方式数;
所以 $P_k(G)=P_k(G-e)-P_k(G\cdot e)$

推论

设 $G$ 是简单图, $e=uv$ 是 $G$ 的一条边, 且 $d(u)=1$, 则:

$$P_k(G)=(k-1)P_k(G-u)$$

证明: 因为 $G$ 是简单图, $e=uv,d(u)=1$, 所以 $G\cdot e=G-u$.

另一方面, $P_k(G-e)=k{P}_k(G-u)$

所以,

$$\begin{array}{rl}{P}_k(G)& =P_k(G-e)-P_k(G\cdot e)\\ & =k{P}_k(G-u)-P_k(G-u)\\ & =(k-1)P_k(G-u)\end{array}$$

对递推公式的使用分析

(1) 当图 $G$ 的边数较少时, 使用减边递推法:

$$P_k(G)=P_k(G-e)-P_k(G\cdot e)$$

(2) 当图 $G$ 的边数较多时, 使用加边递推法:

$$P_k(G-e)=P_k(G)+P_k(G\cdot e)$$

注:

• 重边不影响顶点染色个数, 故直接删去.
• $K_n$ 的色多项式为 $k(k-1)\dots (k-n+1)$;
• $n$ 阶空图的色多项式为 $k^n$.

注: 递推计数法的计算复杂度是指数型的.

例

求出下面各图的色多项式.

解: (1) 加边变成 $K_3$

$$P_k(G_1)=k(k-1)(k-2)+k(k-1)=k^3-2k^2+k$$

也可由推论:

$$P_k(G_1)=(k-1)P_k(K_2)=k^3-2k^2+k$$

(2) 加边变成 $K_4$

$$\begin{array}{rl}{P}_k(G_2)& =k(k-1)(k-2)(k-3)+2k(k-1)(k-2)+k(k-1)\\ & =k(k-1)(k^2-3k+3)\end{array}$$

(3) 删边

$$P_k(G_3)=k(k-1)(k^3-5k^2+10k-7)$$

理想子图计数法

理想子图

设 $H$ 是图 $G$ 的生成子图. 若 $H$ 的每个分支均为完全图, 则称 $H$ 是 $G$ 的一个理想子图. 用 $N_r(G)$ 表示 $G$ 的具有 $r$ 个分支的理想子图的个数.

例

求 $N_4(G),N_5(G)$.

解: 通过观察枚举求 $N_r(G)$.

1) $N_4(G)$:

$N_4(G)=6$.

2) $N_5(G)$:

$N_5(G)=5$.

定理

设 $q_r(G)$ 表示将简单图 $G$ 的顶点集合 $V$ 划分为 $r$ 个不同色类的划分数, 则:

$$q_r(G)=N_r(\overline{G})(1\le r\le |V|)$$

证明: 一方面, 设 $G$ 的任一 $r$ 色划分为: $V_1,V_2,\dots ,V_r$. 于是, 对于 $1\le i\le r$, $\overline{G}[V_i]$ 是 $\overline{G}$ 的完全子图.

因为 $V_i\cap V_j=\Phi (i\ne j)$, 所以 ${\bigcup }_{i=1}^r\overline{G}[V_i]$ 是 $\overline{G}$ 的具有 $r$ 个分支理想子图.

$G$ 的任一个 $r$ 色划分必然唯一对应 $\overline{G}$ 的一个具有 $r$ 个分支理想子图.

所以, $q_r(G)=N_r(\overline{G})(1\le r\le |V|)$.

理想子图法求色多项式

上面定理实际上给我们提供了色多项式的求法. 用 $k$ 种颜色对简单图 $G$ 正常点着色, 那么便有下面的计数公式:

$$P_k(G)=\sum _{i=1}^n{N}_i(\overline{G})[k{]}_i$$

其中, $[k{]}_i=k(k-1)(k-2)\cdots (k-i+1)$.

伴随多项式

设 $G$ 是简单图, 令 $N_i(G)=r_i,[k{]}_i=x^i$ . 称

$$h(G,x)=\sum _{i=1}^n{r}_i{x}^i$$

为图 $G$ 的伴随多项式.

于是, 求 $P_k(G)$ 就是要求出 $\overline{G}$ 的伴随多项式.

★理想子图法求色多项式的步骤

用理想子图法求 $P_k(G)$ 的步骤如下:

(1) 画出 $G$ 的补图 $\overline{G}$.

(2) 求出关于补图的 $r_i=N_i(\overline{G}),(1\le i\le n)$.

(3) 写出关于补图的伴随多项式 $h(\overline{G},x)={\sum }_{i=1}^n{r}_i{x}^i$.

(4) 将 $x^i=[k{]}_i$ 代入伴随多项式中得到 $P_k(G)$.

例

求下图 $G$ 的色多项式 $P_k(G)$.

解: (1) $G$ 的补图为:

(2) 求出关于补图的伴随多项式系数 $r_i(1\le i\le 6)$

i) $i=6,r_6=N_6(\overline{G})=1$
6个分支的理想子图, 每个分支是 $K_1$, 一种

ii) $i=5,r_5=N_5(\overline{G})=5$
5个分支的理想子图, 4个分支是 $K_1$, 1个分支是 $K_2$, 5条边, 5种

iii) $i=4,r_4=N_4(\overline{G})=6$
4个分支的理想子图,
2个分支是 $K_1$, 2个分支是 $K_2$, 5种,
3个分支是 $K_1$, 1个分支是 $K_3$, 1种,
共6种

iv) $i=3,r_3=N_3(\overline{G})=2$
3个分支的理想子图,
3个分支是 $K_2$, 1种,
1个分支是 $K_1$, 1个分支是 $K_2$, 1个分支是 $K_3$, 1种,
共2种

v) $i=2,r_2=N_2(\overline{G})=0$

vi) $i=1,r_1=N_1(\overline{G})=0$

(3) 写出关于补图的伴随多项式

$$h(\overline{G},x)=\sum _{i=1}^n{r}_i{x}^i=2x^3+6x^4+5x^5+x^6$$

(4) 将 $x^i=[k{]}_i$ 代入伴随多项式中得到 $P_k(G)$.

$$\begin{array}{rl}{P}_k(G)& =2[k{]}_3+6[k{]}_4+5[k{]}_5+[k{]}_6\\ & =2k(k-1)(k-2)+6k(k-1)(k-2)(k-3)\\ & +5k(k-1)(k-2)(k-3)(k-4)\\ & +k(k-1)(k-2)(k-3)(k-4)(k-5)\end{array}$$

可以作如下计算:

$$P_1(G)=P_2(G)=0,P_3(G)=12$$

由此可以断定: $\chi (G)=3$. 最优着色方式数有 $12$ 种.

理想子图法求色多项式的改进

使用理想子图法求色多项式, 还可以通过如下定理进行改进:

定理: 若 $G$ 有 $t$ 个分支 $H_1,H_2,\dots H_t$, 且 $H_i$ 的伴随多项式为 $h(H_i,x),i=1,2,\dots ,t$, 则:

$$h(G,x)=\prod _{i=1}^{t}h(H_i,x)$$

该定理说明, 在求 $\overline{G}$ 的伴随多项式时, 可以分别求出它的每个分支的伴随多项式, 然后将它们作乘积 (注: 生成函数方法).

例

求下图 $G$ 的色多项式 $P_k(G)$.

解: (1) 画出 $G$ 的补图 (见上图)

(2) 求出补图中个分支的伴随多项式: $h(H_1,x)=x,h(H_2,x)=x+x^2,h(H_3,x)=x+x^2$

(3) 求出补图的伴随多项式: $h(\overline{G},x)=x(x+x^2{)}^2=x^3+2x^4+x^5$

(4) 求出 $G$ 的色多项式:

$$\begin{array}{rl}{P}_k(G)& =k(k-1)(k-2)+2k(k-1)(k-2)(k-3)\\ & +k(k-1)(k-2)(k-3)(k-4)\\ & =k(k-1)(k-2)(k^2-5k+7)\end{array}$$

注:
(1) 在例4中, $k=3$ 时, $P_3(G)=6$, 由此可以推出 $G$ 的点色数为 $3$.
(2)求出了色多项式, 可以推出点色数. 但是, 求色多项式的计算量是很大的. 递推方法(指数次)和理想子图法(找出所有理想子图很困难)都不是多项式时间算法.计算一般图的色多项式的系数是 #P-complete (难度不亚于NP-完全问题)

色多项式的性质

定理 (Whitney,1933)

$n$ 阶简单图 $G$ 的色多项式 $P_k(G)$ 是常数项为 $0$ 的首 $1$ 整系数多项式, 且各项系数符号正负相间.

注:

(1) 定理的逆不成立! (见下面例1, 例2)

(2) 事实上, 亦可用 Inclusion-Exclusion Principle 证明色多项式, 且可得 $a_2=\left(\genfrac{}{}{0ex}{}{m}{2}\right)-t$, 其中 $t$ 是图中三角形的个数. (Hint: 设性质 $p_i$ 是边 $e_i(1\le i\le m)$ 的两个端点着相同色, 则 $P_k(G)$ 是不具有任一性质的所有着色方案数)

(3) 同构的图具有相同的色多项式, 但逆不真. (见下面例3)

例1

(Whitney,1933) 用递推公式证明: 设 $G=(n,m)$ 是简单图, 则在其色多项式 $P_k(G)$ 中 $k^{n-1}$ 的系数是 $-m$.

证明: 对边数用数学归纳法.

当 $m=1$ 时, $P_k(G)=P_k(G-e)-P_k(G\cdot e)=k^n-k^{n-1}$. 显然, 结论成立.

设命题对少于 $m$ 条边的 $n$ 阶单图成立. 考虑简单图 $G=(n,m)$.

由递推公式: $P_k(G)=P_k(G-e)-P_k(G\cdot e)$.

由假设可令:

$P_k(G-e)=k^n+a_1{k}^{n-1}+\cdots +a_{n-1}k$, 且 $a_1=-m+1$;
$P_k(G\cdot e)=k^{n-1}+b_1{k}^{n-2}+\cdots +b_{n-2}k$ (但 $b_1=-m+1$ 不一定成立);

故: $P_k(G)=k^n+(a_1-1)k^{n-1}+(a_2+b_1)k^{n-2}+\cdots +(a_{n-1}+b_{n-2})k$.

所以, $a_1-1=-m$.

例2

不存在以 $k^4-3k^3+3k^2$ 为其色多项式的简单图.

证明: 事实上, 一方面, 如果它是某简单图的色多项式, 则由多项式本身可以得到点色数为 $1$ (代入 $1$ 后不为零);

另一方面, 由例 1 和多项式本身, 如果多项式是某简单图的色多项式, 则 $m(G)=3$. 于是点色数至少为 $2$ (存在边).

上面导出了矛盾！

例3

求证: 下面图 $G_1$ 与 $G_2$ 不同构但具有相同的色多项式.

证明: 因为 $G$ 和 $H$ 中分别有唯一的 $4$ 度点: $u_1$ 与 $v_1$. 但是它们邻域状况不相同: $u_1$ 有 $4$ 个 $2$ 度邻点, 而 $v_1$ 只有两个 $2$ 度邻点. 显然, $G$ 与 $H$ 不同构.

通过理想子图计算得: $P_k(G)=P_k(H)=2[k{]}_3+4[k{]}_4+[k{]}_5$.

其他性质

对于图的色多项式, 还有许多有趣的特点. 例如系数序列的绝对值满足:

(1) 单峰性 (先增大后减小);

(2) 对数凹性 (对于 $0<i<n$, 不等式 $a_i^2\ge a_{i-1}{a}_{i+1}$ 均成立).