Fractional coloring

Fractional coloring is a topic in a young branch of graph theory known as fractional graph theory.

Fractional graph coloring can be viewed as the linear programming relaxation of traditional graph coloring.

Indeed, fractional coloring problems are much more amenable to a linear programming approach than traditional coloring problems.

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.

Equivalently, it can be defined as a homomorphism to the Kneser graph KGa,b.

is defined to be: Note that the limit exists because

The fractional chromatic number can equivalently be defined in probabilistic terms.

is the smallest k for which there exists a probability distribution over the independent sets of G such that for each vertex v, given an independent set S drawn from the distribution: We have: with equality for vertex-transitive graphs, where n(G) is the order of G, α(G) is the independence number.

Furthermore, the fractional chromatic number approximates the chromatic number within a logarithmic factor,[2] in fact: Kneser graphs give examples where:

of a graph G can be obtained as a solution to a linear program.

For each independent set I, define a nonnegative real variable xI.

The dual of this linear program computes the "fractional clique number", a relaxation to the rationals of the integer concept of clique number.

The strong duality theorem of linear programming guarantees that the optimal solutions to both linear programs have the same value.

Note however that each linear program may have size that is exponential in the number of vertices of G, and that computing the fractional chromatic number of a graph is NP-hard.

[3] This stands in contrast to the problem of fractionally coloring the edges of a graph, which can be solved in polynomial time.

This is a straightforward consequence of Edmonds' matching polytope theorem.

[4][5] Applications of fractional graph coloring include activity scheduling.

Put otherwise, the set of nodes that are active simultaneously must be an independent set in graph G. An optimal fractional graph coloring in G then provides a shortest possible schedule, such that each node is active for (at least) 1 time unit in total, and at any point in time the set of active nodes is an independent set.

If we have a solution x to the above linear program, we simply traverse all independent sets I in an arbitrary order.

time units; meanwhile, each node not in I is inactive.

In more concrete terms, each node of G might represent a radio transmission in a wireless communication network; the edges of G represent interference between radio transmissions.

Each radio transmission needs to be active for 1 time unit in total; an optimal fractional graph coloring provides a minimum-length schedule (or, equivalently, a maximum-bandwidth schedule) that is conflict-free.

If one further required that each node must be active continuously for 1 time unit (without switching it off and on every now and then), then traditional graph vertex coloring would provide an optimal schedule: first the nodes of color 1 are active for 1 time unit, then the nodes of color 2 are active for 1 time unit, and so on.

In general, fractional graph coloring provides a shorter schedule than non-fractional graph coloring; there is an integrality gap.

It may be possible to find a shorter schedule, at the cost of switching devices (such as radio transmitters) on and off more than once.