点着色

• 图的点着色
  图 $G$ 的一种点着色是指：给图 $G$ 的每个顶点涂上一种颜色，使得相邻的顶点具有不同的颜色。

• k着色
  对图 $G$ 进行 $k$ 着色（称 $G$ 是 $k$-可着色的），即能够用 $k$ 种颜色给 $G$ 的顶点着色。

• 图的色数
  图 $G$ 的色数 $\chi(G) = k$，意味着图 $G$ 是 $k$-可着色的，但不是 $(k-1)$-可着色的。即能给图着色的最少颜色数。

色数的上下界

$$\chi(G) \leq \Delta(G) + 1$$
$\chi(K_n) = n$，$\chi(K_{m,n}) = 2$。
$\chi(G) \leq \Delta(G)$，当且仅当 $G$ 不是完全图。（Brooks 定理）
偶圈的色数为 $2$，奇圈的色数为 $3$。
$\chi(W_n) = \begin{cases} 3 & n \text{ 为奇数} \newline 4 & n \text{ 为偶数} \end{cases}$

Welch-Powell 算法

1. 对图的顶点按度数从大到小排序。
2. 从度数最大的顶点开始，给每个顶点涂色，在序列中找到最近且不相邻的顶点的颜色，涂上该颜色。
3. 重复步骤 2，直到所有顶点都被涂色。

在许多实际情况下，Welch-Powell算法的表现非常好，但它不一定会得到图的最小着色数。

地图着色与平面图的点着色

• 地图：联通无桥平面图的平面嵌入与所有的面。
• 国家：地图的面。
• 相邻：两个国家至少有一条公共边。

地图的面着色

• 地图的面着色
  给地图的每个国家涂上一种颜色，使得相邻的国家具有不同的颜色。
• k-面可着色
  能够用 $k$ 种颜色给地图的国家着色。
• 地图的面着色数
  地图的面着色的最少颜色数。记作 $\chi^*(G)$。

地图的面着色转化为对偶图的点着色问题。
地图 $G$ 是 $k$-面可着色的当且仅当对偶图 $G^*$ 是 $k$-可着色的。

四色定理

地图的面着色数 $\chi^*(G) \leq 4$。

边着色

• 图的边着色
  图 $G$ 的一种边着色是指：给图 $G$ 的每条边涂上一种颜色，使得相邻的边具有不同的颜色。
• k-边可着色
  对图 $G$ 进行 $k$ 边着色（称 $G$ 是 $k$-边可着色的），即能够用 $k$ 种颜色给 $G$ 的边着色。
• 图的边着色数
  图 $G$ 的边着色数 $\chi’(G) = k$，意味着图 $G$ 是 $k$-边可着色的，但不是 $(k-1)$-边可着色的。即能给图边着色的最少颜色数。

边着色的上下界

Vizing 定理：对于任意无向简单图 $G$，有 $$\Delta(G) \leq \chi’(G) \leq \Delta(G) + 1$$
$\displaystyle \chi’(K_n) = \begin{cases} n & n \text{ 为奇数} \newline n - 1 & n \text{ 为偶数} \end{cases}$，$\chi’(K_{m,n}) = \Delta$。
$n \ge 4$ 时，$\chi’(W_n) = n - 1$。
偶圈的边着色数为 $2$，奇圈的边着色数为 $3$。