Fractional coloring

Fractional coloring is a topic in a young branch of graph theory known as fractional graph theory. It is a generalization of ordinary graph coloring. In a traditional graph coloring, each vertex in a graph is assigned some color, and adjacent vertices — those connected by edges — must be assigned different colors. In a fractional coloring however, a set of colors is assigned to each vertex of a graph. The requirement about adjacent vertices still holds, so if two vertices are joined by an edge, they must have no colors in common.

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.

Definitions

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. Equivalently, it can be defined as a homomorphism to the Kneser graph KG_a,b. The b-fold chromatic number ${\displaystyle \chi _{b}(G)}$ is the least a such that an a:b-coloring exists.

The fractional chromatic number ${\displaystyle \chi _{f}(G)}$ is defined to be:

${\displaystyle \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 ${\displaystyle \chi _{b}(G)}$ is

${\displaystyle \chi _{a+b}(G)\leq \chi _{a}(G)+\chi _{b}(G).}$

The fractional chromatic number can equivalently be defined in probabilistic terms. ${\displaystyle \chi _{f}(G)}$ 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:

${\displaystyle \Pr(v\in S)\geq {\frac {1}{k}}.}$

Properties

We have:

${\displaystyle \chi _{f}(G)\geq {\frac {n(G)}{\alpha (G)}},}$

with equality for vertex-transitive graphs, where n(G) is the

Moreover:

${\displaystyle \omega (G)\leq \chi _{f}(G)\leq \chi (G),}$

where ω(G) is the

clique number

, and ${\displaystyle \chi (G)}$ is the

chromatic number

.

Furthermore, the fractional chromatic number approximates the chromatic number within a logarithmic factor,[2] in fact:

${\displaystyle {\frac {\chi (G)}{1+\ln \alpha (G)}}\leq \chi _{f}(G)\leq {\frac {\chi _{b}(G)}{b}}\leq \chi (G).}$

Kneser graphs give examples where: ${\displaystyle \chi (G)/\chi _{f}(G)}$ is arbitrarily large, since: ${\displaystyle \chi (KG_{m,n})=m-2n+2,}$ while ${\displaystyle \chi _{f}(KG_{m,n})={\tfrac {m}{n}}.}$

Linear programming (LP) formulation

The fractional chromatic number ${\displaystyle \chi _{f}(G)}$ of a graph G can be obtained as a solution to a linear program. Let ${\displaystyle {\mathcal {I}}(G)}$ be the set of all independent sets of G, and let ${\displaystyle {\mathcal {I}}(G,x)}$ be the set of all those independent sets which include vertex x. For each independent set I, define a nonnegative real variable x_I. Then ${\displaystyle \chi _{f}(G)}$ is the minimum value of:

${\displaystyle \sum _{I\in {\mathcal {I}}(G)}x_{I},}$

subject to:

${\displaystyle \sum _{I\in {\mathcal {I}}(G,x)}x_{I}\geq 1}$

for each vertex ${\displaystyle x}$.

The