Fractional Coloring

Let I(G) denote the set of all independent sets of vertices of a graph G, and let I(G,u) denote the independent sets of G that contain the vertex u. A fractional coloring of G is then a nonnegative real function f on I(G) such that for any vertex u of G,

The sum of values of f is called its weight, and the minimum possible weight of a fractional coloring is called the fractional chromatic number chi^*(G).

The above definition of fractional coloring is equivalent to allowing multiple colors at each vertex, each with a specified weight fraction, such that adjacent vertices contain no two colors alike. For example, while the dodecahedral graph is 3-colorable since the chromatic number is 3 (left figure above; red, yellow, green), it is 5/2-multicolorable since the fractional chromatic number is 5/2 (5 colors-red, yellow, green, blue, cyan-each with weight 1/2, giving 5·(1/2)=5/2).

Note that in fractional coloring, each color comes with a fraction which indicates how much of it is used in the coloring. So if red comes with a fraction 1/4, it counts as 1/4 in the weight. There can therefore be more actual colors used in a fractional coloring than in a non-fractional coloring. For example, as illustrated above, the 5-cycle graph C_5 is 3-vertex chromatic (left figure) but is 5/2-fractional chromatic (middle figure). However, somewhat paradoxically, the fractional coloring of C_5 (right figure) using seven colors still only count as only "5/2 colors" since the colors come with weights 1/2 (red, green, violet) and 1/4 (the other four), giving a fractional chromatic number of

As a result, the question of how to minimize the "actual" number of colors used is not (usually) considered in fractional coloring.

A fractional coloring is said to be regular if for each vertex u of a graph G,

Every graph G has a regular fractional coloring with rational or integer values (Godsil and Royle 2001, p. 138).

See also

Explore with Wolfram|Alpha

References

Referenced on Wolfram|Alpha

Cite this as:

Weisstein, Eric W. "Fractional Coloring." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/FractionalColoring.html

Subject classifications