Fractional Coloring

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

(1)

The sum of values of  is called its weight, and the minimum possible weight of a fractional coloring is called the fractional chromatic number .

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 ).

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  is 3-vertex chromatic (left figure) but is 5/2-fractional chromatic (middle figure). However, somewhat paradoxically, the fractional coloring of  (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

(2)

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  of a graph ,

(3)

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

REFERENCES

Godsil, C. and Royle, G. "Fractional Colourings and Cliques." §7.1 in Algebraic Graph Theory. New York: Springer-Verlag, pp. 135-136, 2001.

Scheinerman, E. R. and Ullman, D. H. Fractional Graph Theory A Rational Approach to the Theory of Graphs. New York: Dover, 2011.