形式陈述

无向图 $G=(V,E)$$G=(V,E)$ 的一个正常顶点 $k$$k$-染色是函数

$$ c:V\to\{1,\ldots,k\} $$$$c:V\to \{1,\dots ,k\}$$

满足每条边 $uv\in E$$uv\in E$ 都有 $c(u)\ne c(v)$$c(u)\ne c(v)$。能这样染色称 $k$$k$-可染；最小可行 $k$$k$ 称色数 $\chi(G)$$\chi (G)$。含自环的图不存在正常染色。无边图色数通常约定为 1（空图的约定可另定），完全图 $K_n$$K_n$ 色数为 $n$$n$；非空图二染色当且仅当它是二分图，当且仅当不含奇环。

直觉

颜色表示互斥资源：相邻顶点不能共享同一资源，目标是用尽可能少的类别同时满足所有局部冲突。

例子与边界

偶环可用两色交替，奇环至少需三色。贪心染色按某个顶点顺序依次选最小可用颜色，最多用 $\Delta+1$$\mathrm{\Delta }+1$ 色，但结果高度依赖顺序且不保证达到 $\chi(G)$$\chi (G)$。地图面染色可转成平面对偶图的顶点染色，但需要正确处理边界邻接。边染色是给边着色的另一问题，不应混同。

推论与应用

图染色建模课程排表、寄存器分配、频率分配和冲突调度。它还连接平面图四色定理、完美图和近似/参数化复杂性。

参考资料

• Reinhard Diestel, Graph Theory, 5th ed., Springer, 2017，Ch. 5, vertex colouring and chromatic number。
• Douglas B. West, Introduction to Graph Theory, 2nd ed., Prentice Hall, 2001，Ch. 5, colorings, critical graphs, and bounds。