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