图着色问题

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

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

图色数

有两个相关的术语：

1. 图色数（chromatic number），也被称为顶点色数（vertex chromatic number），指将一张图上的每个顶点染色，使得相邻的两个点颜色不同，最小需要的颜色数。最小染色数用$\chi (G)$或$\gamma (G)$表示。
2. Template:Le（edge chromatic number）：指将一张图上的每条边染色，使有公共顶点的边颜色不同，最少需要的颜色数叫边色数，用${\chi }^{\prime }(G)$表示。

和图中其他对象的关系

色数和团数（clique number）

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

$\chi (G)\ge \omega (G)$

色数和独立数（independence number）

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

$\frac{n}{\alpha (G)}\le \chi (G)\le 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: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問題列表
• 幾乎完備（Template:Tsl）問題與弱完備（Template:Tsl）問題
• ASR-complete
• Ladner理論
• NP困难
• P/NP问题