图着色问题

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

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

图色数

有两个相关的术语：

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

和图中其他对象的关系

色数和团数（clique number）

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

${\displaystyle \chi (G)\geq \omega (G)}$

色数和独立数（independence number）

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

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

色多项式

全部非同构三阶图和它们的色多项式。空图 E₃(红)可以进行1-着色；其他图不可以。绿色的图用3种颜色有12种染色方法

主条目：色多项式

色多项式用于计算给定数量的颜色下对某图进行涂色的可行方式数。例如，考虑有3个顶点的完全图 ${\displaystyle K_{3}}$，若只使用两种颜色，${\displaystyle K_{3}}$根本无法被着色；若使用三种颜色，则有 ${\displaystyle 3!=6}$ 种方式进行着色；若使用四种颜色，则有 ${\displaystyle P_{3}^{4}=24}$ 个有效着色方案。因此，对于 ${\displaystyle K_{3}}$，有效着色数量的表格将从以下内容开始：

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

色多项式是一个函数，记录将一个图 G 进行 t-着色的方法数，记作 ${\displaystyle P(G,t)}$。正如其名所述，${\displaystyle P(G,t)}$ 是一个关于 t 的多项式。回到上面 ${\displaystyle K_{3}}$ 的例子，事实上，${\displaystyle P(K_{3},t)=t(t-1)(t-2)}$。

显而易见的，色多项式 ${\displaystyle P(G,t)}$ 比图色数蕴涵更多的资讯，更精确的说，${\displaystyle \chi (G)}$ 是色多项式最小的非零解正整数，即

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

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

部分图的色多项式

三角形 K3	${\displaystyle t(t-1)(t-2)}$
完全图 Kn	${\displaystyle t(t-1)(t-2)\cdots (t-(n-1))}$
n个顶点的树	${\displaystyle t(t-1)^{n-1}}$
环 Cn	${\displaystyle (t-1)^{n}+(-1)^{n}(t-1)}$
佩特森图	${\displaystyle 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（英语：Almost complete））问题与弱完备（weakly complete（英语：weakly complete））问题
• ASR-complete
• Ladner理论
• NP困难
• P/NP问题

参考来源

1. Michael R. Garey; D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman. 1979-01-15: 125 [2015-09-21]. ISBN 978-0716710455. （原始内容存档于2016-05-29）.
2. Michael Molloy; Bruce Reed. Graph Colouring and the Probabilistic Method illustrated. Springer Science & Business Media. 2002: 3 [2015-09-22]. ISBN 9783540421399. （原始内容存档于2016-05-28）.