形式陈述

有限无向图 $G=(V,E)$$G=(V,E)$ 的正常顶点着色是映射

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

使每条边 $uv$$uv$ 的端点颜色不同。使这种着色存在的最小正整数 $k$$k$ 称为色数，记作 $\chi(G)$$\chi (G)$。等价地，$V$$V$ 可分割为 $k$$k$ 个独立集。对含至少一个顶点的图，

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

其中 $\omega$$\omega$ 是最大团大小，$\Delta$$\mathrm{\Delta }$ 是最大度；上界由贪心着色得到。图二分当且仅当 $\chi(G)\le2$$\chi (G)\le 2$，且含边二分图的色数恰为二。

直觉

着色把互相冲突的顶点分配到不同资源槽。一个颜色类内部不能有边，所以着色等同于把顶点拆成若干独立组。

例子与边界

完全图 $K_n$$K_n$ 的色数为 $n$$n$；偶圈色数为二，奇圈色数为三。空图（有顶点无边）色数为一；无顶点图有的文献约定色数为零，本条在非空图上使用正整数定义。团下界常不紧：存在团数二但色数任意大的无三角图。贪心算法使用的颜色数依顶点次序，得到至多 $\Delta+1$$\mathrm{\Delta }+1$，不保证最优。色数是顶点着色参数，不要与边色数或列表色数混同。一般图判定 $k$$k$-可着色在固定 $k\ge3$$k\ge 3$ 时是 NP-complete。

推论与应用

色数用于排课、寄存器分配、频谱分配和组合结构复杂度度量。

参考资料

• 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, cliques, and greedy bounds。