图着色问题(Graph Coloring Problem)

图着色问题（英语：Graph Coloring Problem，简称GCP），又称着色问题，是最著名的NP-完全问题之一。

给定一个无向图 $G=(V,E)$，其中 $V$ 为顶点集合，$E$ 为边集合，图着色问题即为将 $V$ 分为 $K$ 个颜色组，每个组形成一个独立集，即其中没有相邻的顶点。其优化版本是希望获得最小的 $K$ 值。

和图着色相关的有四个概念：

• 色数（chromatic number），也被称为顶点色数（vertex chromatic number），指将一张图上的每个顶点染色，使得相邻的两个点颜色不同，最小需要的颜色数。最小染色数用 $\chi(G)$ 表示
• 最大团 的顶点数被称为 $G$ 的团数,表示为 $\omega(G)$

不难证明，色数大于等于团数（染一个最大团就需要 $\omega(G)$ 种不同的颜色），即：

$\chi(G) \geq \omega(G)$

以及

• 团覆盖数，覆盖图的所有顶点所需要的完全子图的最小个数，用 $\kappa(\mathrm{G})$ 表示。
• 最大独立集，它的顶点数被称为 $G$ 的独立数，记为 $\alpha (G)$

也可以证明，团覆盖数大于等于独立数（最大独立集的每个点至少需要一个团来覆盖），即

$\kappa(G) \geq \alpha(G)$

问题难度

• 一般图的二着色问题多项式可解，k(k>=3)着色是 NPC
• 平面图的三着色是 NPC，四着色未知但可解（暴力搜索），无着色是多项式可解的。