<p>Yes.</p>

<p>If I understood correctly, the proof of Theorem 1.6 in <a href="http://dx.doi.org/10.1109/SFCS.2001.959936" rel="nofollow">Khot (2001)</a> establishes that it is NP-hard to distinguish between the following two cases, even if we focus on bounded-degree graphs of sufficiently high degree:</p>

<ol>
<li>There is a $k$-colouring.</li>
<li>The ratio of the number of vertices to the maximum size of an independent set is at least $k^{\log(k)/25}$.</li>
</ol>

<p>From the perspective of fractional chromatic number these two cases are:</p>

<ol>
<li>The fractional chromatic number is at most $k$.</li>
<li>The fractional chromatic number is at least $k^{\log(k)/25}$.</li>
</ol>

<p>Now we must remember that we need sufficiently high degrees (as a function of $k$). But as far as I can see, the proof has, e.g., the following convenient corollary that might already be sufficient for your purposes:</p>

<ul>
<li>Given any constant $\alpha$, there are constants $\Delta$ and $c$ such that the following problem in NP-hard: given a graph $G$ of maximum degree $\Delta$, decide whether the fractional chromatic number of $G$ is at most $c$ or at least $\alpha c$.</li>
</ul>

<p>An of course this already implies that there is no PTAS, unless P = NP.</p>

CC BY-SA 3.0
2011-11-02T15:03:45.617Z
Surely the last corollary has some other modifiers on the constants, otherwise this is very well known for small values of $\Delta$, $c_1$, and $c_2$...
Andrew D. King
CC BY-SA 3.0
2011-11-02T15:10:09.070Z
@AndrewD.King: Right, you can make any of them arbitrarily large, etc. But perhaps you could post an answer that shows that the simple version of the corollary can be derived by using older and easier techniques – I think it would already be sufficient to answer OP's question?
Jukka Suomela
CC BY-SA 3.0
2011-11-02T19:37:11.767Z
@JukkaSuomela I mean that as stated, this does not prove APX-hardness.  E.g. it is well-known (Holyer, SICOMP, 1980) that determining the chromatic index of a cubic graph is NP-hard, meaning that it is NP-hard to determine whether or not the chromatic number of a line graph with maximum degree 4 is 4.

What I think you mean is: Given any constant $k$, there exist constants $\Delta$, $c_1$, and $c_2$ such that $kc_1<c_2$,... Is that right?
Andrew D. King
CC BY-SA 3.0
2011-11-02T19:56:22.060Z
@AndrewD.King: Yes, I'll edit the answer; it'll hopefully make more sense that way. :)
Jukka Suomela
CC BY-SA 3.0
2011-11-02T10:36:47.657Z
2011-11-02T20:01:18.240Z
2011-11-02T20:01:18.240Z
Jukka Suomela
<p>Is it apx-hard to approximate fractional chromatic number on bounded degree graphs?</p>

CC BY-SA 3.0
2011-11-02T10:07:03.840Z
What is _fractional_ chromatic number?
Mohammad Al-Turkistany
CC BY-SA 3.0
2011-11-02T11:30:00.867Z
@MohammadAl-Turkistany: LP relexation of chromatic number, see, e.g., http://en.wikipedia.org/wiki/Fractional_coloring
Jukka Suomela
<cc.complexity-theory><graph-theory><approximation-hardness><graph-colouring><bounded-degree>
Hardness of approximating fractional chromatic number on bounded degree graphs
Ashwinkumar B V
# Hardness of approximating fractional chromatic number on bounded degree graphs

(Asked by: username_0 on 2011-11-02)

Is it apx-hard to approximate fractional chromatic number on bounded degree graphs?

**Tags:** cc.complexity-theory, graph-theory, approximation-hardness, graph-colouring, bounded-degree
> **Comments:**
> **username_1**: What is _fractional_ chromatic number?  
> **username_2**: @MohammadAl-Turkistany: LP relexation of chromatic number, see, e.g., http://en.wikipedia.org/wiki/Fractional_coloring  

---

## 1 answers

### Answer by username_2 on 2011-11-02. Score: 11 | Accepted answer

Yes.

If I understood correctly, the proof of Theorem 1.6 in [Khot (2001)](http://dx.doi.org/10.1109/SFCS.2001.959936) establishes that it is NP-hard to distinguish between the following two cases, even if we focus on bounded-degree graphs of sufficiently high degree:

1. There is a $k$-colouring.
2. The ratio of the number of vertices to the maximum size of an independent set is at least $k^{\log(k)/25}$.

From the perspective of fractional chromatic number these two cases are:

1. The fractional chromatic number is at most $k$.
2. The fractional chromatic number is at least $k^{\log(k)/25}$.

Now we must remember that we need sufficiently high degrees (as a function of $k$). But as far as I can see, the proof has, e.g., the following convenient corollary that might already be sufficient for your purposes:

* Given any constant $\alpha$, there are constants $\Delta$ and $c$ such that the following problem in NP-hard: given a graph $G$ of maximum degree $\Delta$, decide whether the fractional chromatic number of $G$ is at most $c$ or at least $\alpha c$.

An of course this already implies that there is no PTAS, unless P = NP.

> **Comments:**
> **username_3**: Surely the last corollary has some other modifiers on the constants, otherwise this is very well known for small values of $\Delta$, $c_1$, and $c_2$...  
> **username_2**: @AndrewD.King: Right, you can make any of them arbitrarily large, etc. But perhaps you could post an answer that shows that the simple version of the corollary can be derived by using older and easier techniques – I think it would already be sufficient to answer OP's question?  
> **username_3**: @JukkaSuomela I mean that as stated, this does not prove APX-hardness.  E.g. it is well-known (Holyer, SICOMP, 1980) that determining the chromatic index of a cubic graph is NP-hard, meaning that it is NP-hard to determine whether or not the chromatic number of a line graph with maximum degree 4 is 4.  What I think you mean is: Given any constant $k$, there exist constants $\Delta$, $c_1$, and $c_2$ such that $kc_1<c_2$,... Is that right?  
> **username_2**: @AndrewD.King: Yes, I'll edit the answer; it'll hopefully make more sense that way. :)  

---

