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.

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength