色數

圖 的色數是為圖 的頂點著色所需的最少顏色數，使得沒有兩個相鄰的頂點共享相同的顏色 (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)。