Home > Fractional coloring

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

Note that the limit exists because χ_b(G) is subadditive, meaning χ_a+b(G) ≤ χ_a(G) + χ_b(G).

Some properties of χ_b(G):

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. BooksEnthsiast.com.