色数

图 的色数是为图 的顶点着色所需的最少颜色数，使得没有两个相邻的顶点共享相同的颜色 (Skiena 1990, p. 210)，即，获得 k-着色 可能的最小 值。上面展示了示例图中最小着色和色数。

图 的色数最常见的表示法是 (例如，Skiena 1990, West 2000, Godsil 和 Royle 2001, Pemmaraju 和 Skiena 2003)，但偶尔也用 表示。

空图 的色数为 1，而非空 二部图 的色数为 2。

图 的色数也是最小正整数 ，使得 色多项式 。计算 图 的色数是一个 NP-完全问题 (Skiena 1990, pp. 211-212)。或者，用 Harary (1994, p. 127) 的话说，“对于确定任意图的色数，目前还没有方便的方法。” 然而，Mehrotra 和 Trick (1996) 设计了一种列生成算法，用于计算色数和顶点着色，该算法可以快速解决大多数中小尺寸的图。

图的色数计算在 Wolfram 语言 中实现为VertexChromaticNumber[g]。可以使用以下方法获得许多命名图的预计算色数GraphData[graph,"ChromaticNumber"].

图的色数必须大于或等于其 团数。如果对于其每个 导出子图 ， 的色数等于 中成对相邻顶点的最大数量，则该图称为 完美图。 团数 等于色数的图（对其导出子图没有进一步的限制）被称为 弱完美图。

根据定义，图 的 边色数 等于 线图 的色数。

布鲁克斯定理 指出，图的色数最多为 最大顶点度 ，除非该图是 完全图 或奇数 环图，在这种情况下，需要 种颜色。

色数 的图被称为 双色图，色数 的图被称为 三色图。一般来说，色数 的图被称为 k-色图，色数 的图被称为 k-可着色图。

下表给出了某些命名图类的色数。

图
完全图
环图 ,
星图 ,	2
轮图 ,

对于任意两个正整数 和 ，都存在围长至少为 且色数至少为 的图 (Erdős 1961; Lovász 1968; Skiena 1990, p. 215)。

亏格为 的曲面的色数由 希伍德猜想 给出，

其中 是 向下取整函数。 有时也表示为 (这很不幸，因为 通常指的是 欧拉示性数)。对于 , 1, ..., 的前几个值是 4, 7, 8, 9, 10, 11, 12, 12, 13, 13, 14, 15, 15, 16, ... (OEIS A000934)。

Erdős (1959) 证明了存在具有任意大 围长 和色数的图 (Bollobás 和 West 2000)。