Fractional coloring

. A 4:2-coloring ofthis graph does not exist.]

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. It can be viewed as the linear programming relaxation of traditional graph coloring.

A "b"-fold coloring of a graph "G" is an 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

:$chi\_\{f\}(G)\; =\; lim\_\{b\; o\; 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 χ_"f"("G"):

:$chi\_f(G)ge\; n(G)/alpha(G)$and:$omega(G)\; le\; chi\_f(G)\; le\; chi(G)$

Here n("G") is the order of "G", α("G") is the independence number, ω("G") is the clique number, and χ("G") is the chromatic number.

Linear Programming (LP) Formulation

The fractional chromatic number χ_f("G") of a graph "G" can also be obtained as a solution to a linear program. The linear program has a dual that calculates "fractional clique number", a relaxation to the rationals of the integer concept of clique number. The strong duality theorem of linear programming guarantees that solutions to both linear programs do exist. However, each linear program has size that is exponential in the number of vertices of "G", and computing the fractional chromatic number of a graph is NP-hard. This stands in contrast to the problem of fractionally coloring the edges of a graph, which can be solved in polynomial time thanks to the simple structure of the matching polytope.

References

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

*Godsil, Ghris; Royle, Gordon (2001). " Algebraic Graph Theory". New York: Springer-Verlag. ISBN 0-387-95241-1.