与色数有关的几类图以及完美图

⚠ 转载请注明出处：作者：ZobinHuang，更新日期：May 10, 2022

    本作品由 ZobinHuang 采用 知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可，在进行使用或分享前请查看权限要求。若发现侵权行为，会采取法律手段维护作者正当合法权益，谢谢配合。

目录

有特定需要的内容直接跳转到相关章节查看即可。

正在加载目录...

与色数有关的几类图

临界图

    首先我们给出关于临界图的定义: 若对于图 `G` 的任意真子图 `H`，都有 `\chi(H) < \chi(G)`，则称图 `G` 是 (色) 临界图 (Color-critical)。点色数为 `k` 的临界图称为 `k` 临界图 (`k`-critical Graph)。

    如上所示的分别是 3 临界图和 4 临界图。

    临界图具有如下的性质：

`k` 色图均有 `k` 临界子图

    证明:

    这个结论是显然的。如果一个 `k` 色图不是临界图，那么通过删去一部分的点，一定可以得到一个 `k` 临界图；如果 `k` 色图本身是 `k` 临界图，那么它本身就是自己的一个 `k` 临界子图。

    值得注意的是，这个结论并没有好的算法可以用于求解。

每个临界图均为简单连通图

    证明:

    显然图无自环，且删掉平行边中的一条边并不影响原有图的顶点正常着色，因此每个临界图都是简单图。又因为删掉色数较小的分支，剩下部分的图的色数和原图色数相等。因此临界图必连通。

若 `G` 是 `k` 临界图，则 `\delta(G) \ge k-1`

    证明:

    若不然，`\delta(G) < k-1`，设 `d(v)=\delta`，因为 `G` 是 `k` 临界图，所以 `G-v` 是 `k-1` 可正常顶点着色的。设 `\pi` 是 `G-v` 的 `k-1` 正常顶点着色方案。由于 `d(v) < k-1`，也即点 `v` 的邻居小于 `k-1` 个，显然 `\pi` 可以扩充为 `G` 的 `k-1` 正常顶点着色方案，这与 `G` 是 `k` 临界图相矛盾。

    由上述定理可以得到如下推论:

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

    证明:

    因为 `G` 是 `k` 色图，因此它包含 `k` 临界子图 `G_1`。所以基于 4，可以得到结论 `\delta(G_1) \ge k-1`，即 `G_1` 中至少有 `k` 个顶点，其度数不小于 `k-1`。所以，`G` 中至少有 `k` 个顶点，其度数不小于 `k-1`。

临界图没有割点

    证明:

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

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

    所以只要 `G` 是临界图，它就一定没有割点。

给出三个特殊情况:

1. 仅有的 `1` 临界图是 `K_1`;
2. 仅有的 `2` 临界图是 `K_2`;
3. 仅有的 `3` 临界图是奇圈

    证明:

    由于 `1` 色图是只有一个点的图，因此 `1` 临界图只能是 `K_1`。

    `2` 色图是二部图，所以 `2` 临界图只能是最小的二部图 `K_2`。

    `3` 色图必然含有奇圈，而奇圈本身的色数就是 `3`，所以 `3` 临界图只能是 `3` 色图删去其它 "干扰点" 的奇圈。

不含三角形的 `k` 色图

    我们首先给出定义: 若图 `G` 的点色数是 `k`，且 `G` 中不含有三角形，则称 `G` 是一个 不含三角形的 `k` 色图 (Triangle-free `k`-critical Graph)。

    如上所示的分别是不含三角形的 3 色图和 4 色图。

    下面不加证明地给出关于不含三角形的 `k` 色图的定理:

对于任意正整数 `k`，存在不含三角形的 `k` 色图

完美图简介

    下面我们分别从两个角度对图的完美图作出定义。

关于色数的完美图

    若简单图 `G` 的一个顶点子集 `S` 在 `G` 中的导出子图是完全图，则称 `S` 是 `G` 的一个 团 (Clique)。简单图 `G` 最大团包含的顶点数称为 `G` 的 团数 (Clique Number)，记为 `cl(G)`，即:

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

    显然，图 `G` 的点色数和团数的关系为:

`\chi(G) \ge cl(G)`

    设 `G` 是一个图，若对于 `G` 的每个点导出子图 `H`，均有 `\chi(G) = cl(H)`，则称 `G` 为 完美图 (Perfect Graph)，并且由于我们是基于色数所给出的完美图定义，因此我们也把这种完美图定义称为 基于色数的完美图。

    例如，`K_n` 和 二部图等都是完美图，而不含三角形但含奇圈的图不是完美图，因为不含三角形的但含奇圈的图的团数为 `2`，但色数为 `3`。

关于点独立集的完美图

    设 `G` 是一个图，由 `G` 中互不邻接的顶点作成的子集称为 `G` 的一个 点独立集 (Independent Set)。`G` 中含顶点数最多的点独立集称为 `G` 的 最大独立集，其包含的顶点数称为 独立数 (Independence Number)，记为 `\alpha(G)`。

    设 `S={S_1, S_2, ..., S_u}` 是图 `G` 的顶点集合的一个划分，如果 `S` 的每个子集 `S_i` 在 `G` 中的导出子图均是完全图，则称 `S` 是 `G` 的一个完全分类。`G` 的最小完全分类所包含的元素个数称为 `G` 的 完全数，记为 `\theta(G)`，即:

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

    值得注意的是，我们可以得到 `\alpha(G) \le \theta(G)`，这是因为独立集 `D` 中任意一个点 `v_i` 应该属于 `S` 中的某个顶点子集 `S_j`，同时 `S` 中的每个子集 `S_j` 最多包含独立集中的一个元素 `v_i`。

    基于上述关于独立数和完全数的定义，若对 `G` 中每个点导出子图 `H`，都有 `\alpha(H)=\theta(H)`，则称 `G` 是 关于点独立集的完美图。

完美图定理

    下面我们基于上面两种完美图的定义，不加证明地给出给出完美图定理:

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

    上述定理有如下推论:

`G` 是完美图当且仅当其补图是完美图

关于完美图的结构研究

    而关于完美图的结构问题，有如下 强完美图定理:

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