Fractional coloring

Fractional coloring is a topic in a young branch of graph theory known as fractional graph theory. It differs from the traditonal graph theory 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 factional chromatic number χ_f(G) is defined to be

$\chi _{f}(G)=\lim _{b\to \infty }{\frac {\chi _{b}(G)}{b}}=\inf _{b}{\frac {\chi _{b}(G)}{b}}$

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

Some properties of χ_b(G):

1. χ_b(G) ≥ n(G)/α(G), where n(G) is the order; and α(G), the independence number.

References

• Scheinerman, Edward R.; Ullman, Daniel H. (1997). Factional graph theory. New York: Wiley-Interscience. ISBN 0-471-17864-0.