最后更新: 2025-01-22 09:36 ● 参与者查看: 15 次纠错分享参与项目词条搜索

顶点着色

9.2 顶点着色

在这一节中，我们叙述一般图的顶点着色的概念。
定义9．4（顶点着色）设 $G$ 是一个没有自环的图，对 $G$ 的每个顶点着色，使得没有两个相邻的顶点着上相同的颜色，这种着色称为图的正常着色。图 $G$ 的顶点可用 $k$ 种颜色正常着色，称 $G$ 为 $k$－可着色的。使 $G$ 是 $k$－可着色的数 $k$ 的最小值称为 $G$ 的色数，记为 $\chi ( G )$ 。如果 $\chi(G)=k$ ，则称 $G$ 是 $k$ 色的。

例 9.1 （考试安排问题）某学校有 $n$ 门选修课程需要进行期末考试，同一个学生不能在同一天里参加两门课程的考试。问：该校的期末考试至少要几天？

解：建立一个图论模型表示这一问题：设该学校有 $n$ 门选修课 $x_1, \cdots, x_n$ ，构造图 $G(V, E)$ ， $V=\left\{x_1, \cdots, x_n\right\},\left\{x_i, x_j\right\} \in E$ 当且仅当 $x_i$ 和 $x_j$ 被同一位学生选修。

考试需要的最少天数等于 $G$ 的色数 $x(G)$ 。
设 $G$ 是连通，没有自环的图，如果有多重边，则可删去多重边，用一条边代替，因此下面考虑连通简单图 $G$ 。

有几类图的色数是很容易决定的。
定理9．6（1）$G$ 是零图当且仅当 $x(G)=1$ 。
（2）对于完全图 $K_n, x\left(K_n\right)=n$ ，而 $x\left(\overline{K_n}\right)=1$ 。
（3）对于 $n$ 个顶点构成的回路 $G_n$ ，当 $n$ 是偶数时，$x\left(G_n\right)=2$ ；当 $n$ 是奇数时，$x\left(G_n\right)=3$ 。

（4）$G$ 是二分图当且仅当 $x(G)=2$ 。
证明可以由定义很容易地给出。
对于顶点数 $n \geqslant 3$ 的图的着色特征至今没有得出，然而我们可以给出其色数上界。
定理 9.7 如果图 $G$ 的顶点最大度数为 $\Delta(G)$ ，则 $x(G) \leqslant 1+\Delta(G)$ 。
证明：只要证明图 $G$ 是 $1+\Delta(G)$－可着色的。对 $G$ 的顶点数采用归纳法。当 $n=2$ 时，$G$只有一条边，$\Delta(G)=1, G$ 是 2 －可着色的。所以 $x(G) \leqslant 1+\Delta(G)$ 。假设对于 $n-1$ 个顶点的图，结论成立。现在设 $G$ 有 $n$ 个顶点，顶点的最大度数是 $\Delta(G)$ ，如果删去任意一点 $v$ 及其相关联的边，得到 $n-1$ 个顶点的图 $G^{\prime}$ ，它的最大顶点度数至多是 $\Delta\left(G^{\prime}\right)$ ，且 $\Delta\left(G^{\prime}\right) \leqslant \Delta(G)$ 。根据归纳假设，该图是 $1+\Delta(G)$－可着色的，再将 $v$ 及其相关联的边加回该图，得到图 $G$ ，顶点 $v$的度数至多是 $\Delta(G), v$ 的相邻顶点最多着上 $\Delta(G)$ 种颜色，然后 $v$ 着上第 $1+\Delta(G)$ 种颜色。因此，$G$ 是 $1+\Delta(G)-$ 可着色的。

定理 9.7 的上界是很弱的，例如 $G$ 是二分图时，$\chi(G)=2$ ，而 $\chi(G)$ 可以取得相当大。
1941 年，布鲁克斯（Brooks）证明：使 $\chi(G)=1+\Delta(G)$ 的图只有两类：或者是奇回路，或者是完全图。布鲁克斯定理如下，证明从略。

定理 9.8 如果连通图 $G$ 的顶点的最大度数为 $\Delta(G), G$ 不是奇回路，又不是完全图，则 $\chi(G) \leqslant \Delta(G)$ 。

上一篇：对偶图

下一篇：平面图的着色

本文对您是否有用？有用 (0) 无用 (0)