图着色问题

图着色问题（英語：Graph Coloring Problem，簡稱GCP），又称着色问题，是最著名的NP-完全问题之一^[1]。

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

图色数编辑

有两个相关的术语：

图色数（英語：chromatic number），也被称为顶点色数（vertex chromatic number），指将一张图上的每个顶点染色，使得相邻的两个点颜色不同，最小需要的颜色数。最小染色数用 $\chi (G)$ 或 $\gamma (G)$ 表示。
边色数（英语：Edge chromatic number）（edge chromatic number）：指将一张图上的每条边染色，使有公共顶点的边颜色不同，最少需要的颜色数叫边色数，用 $\chi '(G)$ 表示。