圖着色問題

圖着色問題（英語：Graph Coloring Problem，簡稱GCP），又稱着色問題，是最著名的NP-完全問題之一。

給定一個無向圖$G=(V,E)$，其中$V$為頂點集合，$E$為邊集合，圖着色問題即為將$V$分為$K$個顏色組，每個組形成一個獨立集，即其中沒有相鄰的頂點。其優化版本是希望獲得最小的$K$值。

圖色數

有兩個相關的術語：

1. 圖色數（英語：chromatic number），也被稱為頂點色數（vertex chromatic number），指將一張圖上的每個頂點染色，使得相鄰的兩個點顏色不同，最小需要的顏色數。最小染色數用$\chi (G)$或$\gamma (G)$表示。
2. 邊色數（edge chromatic number）：指將一張圖上的每條邊染色，使有公共頂點的邊顏色不同，最少需要的顏色數叫邊色數，用$\chi '(G)$表示。

和圖中其他對象的關係

色數和團數（clique number）

團（英語：clique）是一個圖中兩兩相鄰的頂點構成的集合。最大團是一個圖中頂點最多的團，它的頂點數被稱為$G$的團數，記為$\omega (G)$。$\omega (G)$和$\chi (G)$滿足如下關係：

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

色數和獨立數（independence number）

獨立集（英語：independent set）是一個圖中兩兩不相鄰的頂點所構成的集合。最大獨立集是一個圖中頂點最多的獨立集，它的定點數被稱為$G$的獨立數，記為$\alpha (G)$。$\alpha (G)$和$\chi (G)$滿足如下關係：

${\frac {n}{\alpha (G)}}\leq \chi (G)\leq n-\alpha (G)+1$

色多項式

全部非同構三階圖和它們的色多項式。空圖 E₃(紅)可以進行1-着色；其他圖不可以。綠色的圖用3種顏色有12種染色方法

主條目：色多項式

色多項式用於計算給定數量的顏色下對某圖進行塗色的可行方式數。例如，考慮有3個頂點的完全圖 $K_{3}$，若只使用兩種顏色，$K_{3}$根本無法被着色；若使用三種顏色，則有 $3!=6$ 種方式進行着色；若使用四種顏色，則有 $P_{3}^{4}=24$ 個有效着色方案。因此，對於 $K_{3}$，有效着色數量的表格將從以下內容開始：

可使用之顏色數	1	2	3	4	…
有效着色方法數	0	0	6	24	…

色多項式是一個函數，記錄將一個圖 G 進行 t-着色的方法數，記作 $P(G,t)$。正如其名所述，$P(G,t)$ 是一個關於 t 的多項式。回到上面 $K_{3}$ 的例子，事實上，$P(K_{3},t)=t(t-1)(t-2)$。

顯而易見的，色多項式 $P(G,t)$ 比圖色數蘊涵更多的資訊，更精確的說，$\chi (G)$ 是色多項式最小的非零解正整數，即

$\chi (G)=\min\{k\,\colon \,P(G,k)>0\}.$

下表給出了部分圖的色多項式：

部分圖的色多項式

三角形 K3	$t(t-1)(t-2)$
完全圖 Kn	$t(t-1)(t-2)\cdots (t-(n-1))$
n個頂點的樹	$t(t-1)^{n-1}$
環 Cn	$(t-1)^{n}+(-1)^{n}(t-1)$
佩特森圖	$t(t-1)(t-2)(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t-352)$

重要定理

• 五色定理
• 四色定理
• Vizing定理
• 布魯克定理
• Konig定理（關於二分圖）
• Hadwiger猜想
• 拉姆齊定理
• 色數

參見

• NP-complete問題列表
• 幾乎完備（Almost complete）問題與弱完備（weakly complete）問題
• ASR-complete
• Ladner理論
• NP困難
• P/NP問題