分数着色

令 表示图 的所有独立集的集合，令 表示包含顶点 的图 的独立集。图 的分数着色是一个非负实函数 ，定义在 上，使得对于图 的任意顶点 ，

(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)。