分数边色数

图 的分数边色数是 边色数 的分数 аналог，由 Scheinerman 和 Ullman (2011) 记为 。它可以定义为

(1)

其中 是 的 分数色数，而 是 的 线图。

存在计算分数边色数的多项式时间算法 (Scheinerman 和 Ullman 2011, pp. 86-87)。

如果图的 边色数 等于其 最大顶点度 (即，如果图是 1 类图)，则分数边色数也等于 。这遵循分数对象的一般原则：

(2)

以及事实：

(3)

(Scheinerman 和 Ullman 2011, p. 80)，因此结合起来得到

(4)

因此，如果 ，则 。

由于任何 顶点传递图 要么具有 完美匹配（对于偶数顶点度），要么具有近乎完美的匹配（对于奇数顶点度；Godsil 和 Royle 2001, p. 43），并且每个 顶点传递图 的 分数色数 由顶点数除以其 独立数 给出，将上述内容应用于 线图 意味着 对称图 （即，既是顶点传递又是 边传递 的图）的分数边色数由下式给出：

(5)

其中 是 顶点数， 是 的 边数 (S. Wagon, 私人通信，6 月 6, 2012)。

花 Snark 图 是一个图的示例，对于该图，边色数 和分数边色数 都是整数，但 (Scheinerman 和 Ullman 2001, p. 96)。