Fractional Coloring
المؤلف:
Godsil, C. and Royle, G
المصدر:
"Fractional Colourings and Cliques." §7.1 in Algebraic Graph Theory. New York: Springer-Verlag,
الجزء والصفحة:
...
27-3-2022
1857
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.
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
