点着色

给图 $G$ 的每个顶点涂上一种颜色, 使得相邻顶点具有不同颜色.

如果 $G$ 能用 $k$ 种颜色对顶点进行着色, 则称 $G$ 是 $k$- 可着色的.

$G$ 的色数 $\chi (G)=k$, $G$ 是 $k$- 可着色的, 但不是 $(k-1)$- 可着色的.

定理 对于任意无向图 $G$, $\chi (G)\le \Delta (G)+1$.

定理 若连通无向图 $G$ 不是 $K_n$, 也不是奇 圈, 则 $\chi (G)\le \Delta (G)$.

• $\chi (G)=1$ 当且仅当 $G$ 为零图.
• $\chi (K_n)=n$.
• 若 $G$ 为偶 圈, 则 $\chi (G)=2$, 若 $G$ 为奇圈或奇阶 轮图, 则 $\chi (G)=3$.
• 若 $G$ 的边集非空, $\chi (G)=2$ 当且仅当 $G$ 为 二部图.

韦尔奇鲍威尔法

1. 将 $G$ 中的结点按度数递减的次序排序.
2. 用第一种颜色, 对第一点着色, 并按排列次序对与前面结点不相邻的每一点进行同样的着色.
3. 用第二种颜色对尚未着色的点重复第二步.

并不总能得到最少颜色数目的着色方法.

指向原始笔记的链接