图着色问题

图着色问题（，簡稱），又称着色问题，是最著名的NP-完全问题之一。

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

 图色数 
有两个相关的术语：

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

和图中其他对象的关系
色数和团数（clique number）

团（clique）是一个图中两两相邻的顶点构成的集合。最大团是一个图中顶点最多的团，它的顶点数被称为的团数，记为。和满足如下关系：

色数和独立数（independence number）

独立集（independent set）是一个图中两两不相邻的顶点所构成的集合。最大独立集是一个图中顶点最多的独立集，它的定点数被称为的独立数，记为。和满足如下关系：

色多项式

色多項式用於計算給定數量的顏色下對某圖進行塗色的可行方式數。例如，考慮有3個頂點的完全圖 ，若只使用兩種顏色，根本無法被著色；若使用三種顏色，則有  種方式進行著色；若使用四種顏色，則有  個有效著色方案。因此，對於 ，有效著色數量的表格將從以下內容開始：
可使用之顏色數1234...有效著色方法數00624...
色多项式是一個函數，記錄将一个图 G 进行 t-着色的方法数，记作 。正如其名所述， 是一個关于 t 的多项式。回到上面  的例子，事實上，。

顯而易見的，色多項式  比圖色數蘊涵更多的資訊，更精確的說， 是色多項式最小的非零解正整數，即

下表给出了部分图的色多项式：

+部分图的色多项式 三角形 K3   完全图 Kn   n个顶点的树   环 Cn  佩特森图  

 重要定理 

 五色定理
 四色定理
 Vizing定理
 布鲁克定理
 Konig定理（关于二分图）
 Hadwiger猜想
 拉姆齐定理
色数

 参见 
 NP-complete問題列表
 幾乎完備（）問題與弱完備（）問題
 ASR-complete
 Ladner理論
 NP困难
 P/NP问题

 參考來源 

Category:图染色
Category:NP完全问题