設 為圖
的 分數著色。則
的值之和稱為其權重,而分數著色的最小可能權重稱為分數色數
,有時也表示為
(Pirnazar 和 Ullman 2002, Scheinerman 和 Ullman 2011) 或
(Larson et al. 1995),有時也稱為集合色數 (Bollobás 和 Thomassen 1979)、終極色數 (Hell 和 Roberts 1982) 或多重著色數 (Hilton et al. 1973)。每個簡單圖都有一個分數色數,它是有理數或整數。
圖的分數色數可以使用線性規劃獲得,儘管計算是 NP-困難的。
任何樹和任何二分圖的分數色數都是 2 (Pirnazar 和 Ullman 2002)。
分數色數滿足
|
(1)
|
其中 是 團數,
是 分數團數,
是 色數 (Godsil 和 Royle 2001, pp. 141 和 145),其中結果
來自線性規劃的強對偶定理 (Larson et al. 1995; Godsil 和 Royle 2001, p. 141)。
圖的分數色數可能是一個小於色數的整數。例如,對於 Chvátal 圖, 但
。大於 1 的整數差也是可能的,例如,至少四個 28 個頂點的非 Cayley 頂點傳遞圖具有
,並且許多 Kneser 圖具有更大的整數差。
Gimbel et al. (2019) 推測,每個 4 色 平面圖 的分數色數嚴格大於 3。反例由 18 節點的 Johnson 骨架圖 以及 Chiu et al. (2021) 給出的上述 18 節點示例提供。Chiu et al. (2021) 進一步證明,恰好有 17 個具有 色數 4 和分數色數 3 的 4-正則 18 頂點平面圖,並且沒有更小的圖具有這些值。
對於任何圖 ,
|
(2)
|
其中 是 頂點計數,
是
的 獨立數。對於 頂點傳遞
,等式始終成立,在這種情況下
|
(3)
|
(Scheinerman 和 Ullman 2011, p. 30)。但是,對於非頂點傳遞圖,等式也可能成立,包括 路徑圖 、爪形圖
、菱形圖等。
下表給出了特殊圖類的分數色數的閉合形式,其中 Mycielski 圖 由 Larsen et al. (1995) 討論,迴圈圖
由 Scheinerman 和 Ullman (2011, p. 31) 討論,Kneser 圖
由 Scheinerman 和 Ullman (2011, p. 32) 討論。
| 圖 | 分數色數 |
| 迴圈圖 | |
| Kneser 圖 | |
| Mycielski 圖 |
下表給出了其他特殊情況。
| 反稜柱圖 | 3, 4, 10/3, 3, 7/2, 16/5, 3, 10/3, 22/7, ... | |
| 啞鈴圖 | A000027 | 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, ... |
| 雞尾酒會圖 | A000027 | 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, ... |
| 完全圖 | A000027 | 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, ... |
| 迴圈圖 | A141310/A057979 | 3, 2, 5/2, 2, 7/3, 2, 9/4, 2, 11/5, 2, 13/6, ... |
| 空圖 | A000012 | 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ... |
| 頭盔圖 | 4, 3, 7/2, 3, 10/3, 3, 13/4, 3, ... | |
| Mycielski 圖 | A073833/A073834 | 2, 5/2, 29/10, 941/290, 969581/272890, ... |
| 平底鍋圖 | A141310/A057979 | 3, 2, 5/2, 2, 7/3, 2, 9/4, 2, 11/5, 2, 13/6, ... |
| 稜柱圖 | A141310/A057979 | 3, 2, 5/2, 2, 7/3, 2, 9/4, 2, 11/5, 2, 13/6, ... |
| 太陽圖 | A000027 | 3, 4, 5, 6, 7, 8, 9, 10, 11, ... |
| 日卸圖 | A141310/A057979 | 3, 2, 5/2, 2, 7/3, 2, 9/4, 2, 11/5, 2, 13/6, ... |
| 網圖 | 5/2, 2, 9/4, 2, 13/6, 2, 17/8, 2, 21/10, 2, 25/12, ... | |
| 輪圖 | 4, 3, 7/2, 3, 10/3, 3, 13/4, 3, 16/5, 3, 19/6, 3, ... |