TOPICS
Search

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,

 sum_(S in I(G,u))f(S)>=1.
(1)

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

FractionalColoring

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

FractionalColoring2

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

 chi^*(C_5)=3·1/2+4·1/4=5/2.
(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 u of a graph G,

 sum_(S in I(G,u))f(S)=1.
(3)

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


See also

Chromatic Number, Fractional Chromatic Number, Minimum Vertex Coloring, Vertex Coloring

Explore with Wolfram|Alpha

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.

Referenced on Wolfram|Alpha

Fractional Coloring

Cite this as:

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

Subject classifications