Fractional coloring
|
|
Fractional coloring is a topic in a young branch of graph theory known as fractional graph theory. It differs from the traditional graph coloring in the sense that it assigns sets of colors instead of colors to elements.
A b-fold coloring of a graph G is a assignment of sets of size b to vertices of a graph such that adjacent vertices receive disjoint sets. An a:b-coloring is a b-fold coloring out of a available colors. The b-fold chromatic number χb(G) is the least a such that an a:b-coloring exists.
The fractional chromatic number χf(G) is defined to be
- <math>\chi_{f}(G) = \lim_{b \to \infty}\frac{\chi_{b}(G)}{b} = \inf_{b}\frac{\chi_{b}(G)}{b}<math>
Note that the limit exists because χb(G) is subadditive, meaning χa+b(G) ≤ χa(G) + χb(G).
Some properties of χb(G):
- <math>\chi_b(G)\ge n(G)/\alpha(G).<math>
Here n(G) is the order of G; and α(G), the independence number.
References
- Scheinerman, Edward R.; Ullman, Daniel H. (1997). Fractional graph theory. New York: Wiley-Interscience. ISBN 0-471-17864-0.