着色

点着色

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

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

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

色数的上下界

$$\chi (G)\le \mathrm{\Delta }(G)+1$$

$\chi (K_n)=n$，$\chi (K_{m,n})=2$。 $\chi (G)\le \mathrm{\Delta }(G)$，当且仅当 $G$ 不是完全图。（Brooks 定理） 偶圈的色数为 $2$，奇圈的色数为 $3$，偶阶轮图的色数为 $4$。

Welch-Powell 算法

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

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

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

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

地图的面着色

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

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

四色定理

地图的面着色数 ${\chi }^{\ast }(G)\le 4$。

边着色

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

边着色的上下界

Vizing 定理：对于任意无向简单图 $G$，有

$$\mathrm{\Delta }(G)\le {\chi }^{\prime }(G)\le 2\mathrm{\Delta }(G)$$

${\displaystyle {\chi }^{\prime }(K_n)=\{\begin{array}{ll}n-1& n\text{ 为奇数}\\ n& n\text{ 为偶数}\end{array}}$，${\chi }^{\prime }(K_{m,n})=\mathrm{\Delta }$。 $n\ge 4$ 时，${\chi }^{\prime }(W_n)=n-1$。 偶圈的边着色数为 $2$，奇圈的边着色数为 $3$。