<p>I want to find a reference for the following statement. Here, <span class="math-container">$\chi_f(G)$</span> denotes the <em>fractional chromatic number</em> of a graph <span class="math-container">$G$</span>.</p>
<blockquote>
<p>For every fixed <span class="math-container">$r&gt;2$</span>, deciding <span class="math-container">$\chi_f(G) \leq r$</span> for a given graph <span class="math-container">$G$</span> is NP-complete.</p>
</blockquote>
<p>This was written in the <em>Fractional Graph Theory</em> by Edward R. Scheinerman and Daniel H. Ullman.
They refer to the following paper as a reference for this statement:</p>
<blockquote>
<p>M. Grötschel, L. Lovász, and A. Schrijver: <em>The ellipsoid method and its consequences in combinatorial optimization</em>, Combinatorica 1 (1981), no. 2, pp. 169–197, doi <a href="https://doi.org/10.1007/BF02579273" rel="nofollow noreferrer">10.1007/BF02579273</a>, <a href="https://ir.cwi.nl/pub/10046/10046D.pdf" rel="nofollow noreferrer">free copy</a>.</p>
</blockquote>
<p>But in my understanding, this paper only proved the following:</p>
<blockquote>
<p>For given <span class="math-container">$G$</span> and <span class="math-container">$r&gt;0$</span>, deciding <span class="math-container">$\chi_f(G) \leq r$</span> is NP-hard.</p>
</blockquote>
<p>Is there some more clear reference for it?</p>

CC BY-SA 4.0
2024-04-07T14:18:28.140Z
GLS article shows the hardness of "weighted" fractional chromatic number. For the unweighted version this answer seems to be relevant https://cstheory.stackexchange.com/questions/8791/hardness-of-approximating-fractional-chromatic-number-on-bounded-degree-graphs
Chandra Chekuri
CC BY-SA 4.0
2024-04-07T14:34:35.043Z
See also article of Lund and Yannakakis who establish APX-hardness of fractional chromatic number under the standard P \neq NP assumption for bounded values of fractional chromatic number. https://dl.acm.org/doi/10.1145/185675.306789
Chandra Chekuri
<cc.complexity-theory><graph-colouring>
Hardness of deciding fractional chromatic number at most $k$
Minsoo Kim
# Hardness of deciding fractional chromatic number at most $k$

(Asked by: username_0 on 2024-04-05)

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](https://doi.org/10.1007/BF02579273), [free copy](https://ir.cwi.nl/pub/10046/10046D.pdf).

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?

**Tags:** cc.complexity-theory, graph-colouring

> **Comments:**
> **username_1**: GLS article shows the hardness of "weighted" fractional chromatic number. For the unweighted version this answer seems to be relevant https://cstheory.stackexchange.com/questions/8791/hardness-of-approximating-fractional-chromatic-number-on-bounded-degree-graphs  
> **username_1**: See also article of Lund and Yannakakis who establish APX-hardness of fractional chromatic number under the standard P \neq NP assumption for bounded values of fractional chromatic number. https://dl.acm.org/doi/10.1145/185675.306789  

---

## 0 answers

