设 为图
的 分数着色。则
的值之和称为其权重,而分数着色的最小可能权重称为分数色数
,有时也表示为
(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, ... |