Is there any efficient progam or software to calculate the fractional chromatic number?

278 Views Asked by At

The fractional chromatic number $\chi_f(G)$ is a generation of the chromatic number of a graph $G$. It can be formulated as a linear programming question:

Let $\mathcal{I}(G)$ be the set of all independent sets of $G$, and let $\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 $\chi_f(G)$ is the minimum value of $$ \sum_{I\in\mathcal{I}(G)} x_I, $$ subject to $\sum_{I\in\mathcal{I}(G,x)} x_I \ge 1$ for each vertex $x$.

I wrote a linear program to do this thing but it is very slow. So, I'd like to know is there any efficient progam or software to calculate the fractional chromatic number? I have googled with no answer.