分數著色

令 表示圖 的所有獨立集的集合，令 表示包含頂點 的圖 的獨立集。圖 的分數著色是一個非負實函式 ，定義在 上，使得對於圖 的任意頂點 ，

(1)

的值之和稱為其權重，分數著色的最小可能權重稱為分數色數 。

上述分數著色的定義等價於允許每個頂點使用多種顏色，每種顏色都有指定的權重分數，使得相鄰頂點不包含相同的兩種顏色。例如，雖然十二面體圖是 3-可著色的，因為色數是 3（上圖左側；紅色、黃色、綠色），但它是 5/2-多可著色的，因為分數色數是 5/2（5 種顏色 - 紅色、黃色、綠色、藍色、青色 - 每種顏色權重為 1/2，得到 ）。

請注意，在分數著色中，每種顏色都帶有一個分數，表示在著色中使用了多少。因此，如果紅色帶有的分數是 1/4，則在權重中計為 1/4。因此，分數著色中使用的實際顏色可能比非分數著色中使用的顏色更多。例如，如上圖所示，5-圈圖 是 3-頂點色數的（左圖），但它是 5/2-分數色數的（中圖）。然而，有點自相矛盾的是，使用七種顏色對 進行分數著色（右圖）仍然只算作“5/2 種顏色”，因為這些顏色的權重為 1/2（紅色、綠色、紫色）和 1/4（其他四種），從而得到分數色數為

(2)

因此，在分數著色中，通常不考慮如何最小化使用的“實際”顏色數量的問題。

如果對於圖 的每個頂點 ，分數著色被稱為是正則的

(3)

每個圖 都存在一個具有有理數或整數值的正則分數著色 (Godsil and Royle 2001, p. 138)。