3
$\begingroup$

I want to find a reference for the following statement. Here, $\chi_f(G)$ denotes the fractional chromatic number of a graph $G$.

For every fixed $r>2$, deciding $\chi_f(G) \leq r$ for a given graph $G$ is NP-complete.

This was written in the Fractional Graph Theory by Edward R. Scheinerman and Daniel H. Ullman. They refer to the following paper as a reference for this statement:

M. Grötschel, L. Lovász, and A. Schrijver: The ellipsoid method and its consequences in combinatorial optimization, Combinatorica 1 (1981), no. 2, pp. 169–197, doi 10.1007/BF02579273, free copy.

But in my understanding, this paper only proved the following:

For given $G$ and $r>0$, deciding $\chi_f(G) \leq r$ is NP-hard.

Is there some more clear reference for it?

Improve this question
$\endgroup$
2

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.