图着色问题

有两个相关的术语：

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}$ 

色多项式（英语：chromatic polynomial）是将一个图G进行t-着色的方法数，记作P(G, t)。P(G, t)是关于t的多项式，假设G的阶数为n，则P(G, t)满足如下性质：

首项系数为1；

n-1次项系数等于-|E(G)|；

0次项系数等于0；

各项系数正负交替；

一次项系数不为零当且仅当G连通。

色多项式包含了G是否能进行t-着色的信息，即可以根据色多项式确定G的色数。二者具有如下关系：

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

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

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

• NP-complete问题列表
• 几乎完备（Almost complete（英语：Almost complete））问题与弱完备（weakly complete（英语：weakly complete））问题
• ASR-complete
• Ladner理论
• NP困难
• P/NP问题