<p>There are much stronger results for approximate graph coloring.</p>
<ul>
<li><p>S. Khot, <a href="http://www.cs.nyu.edu/%7Ekhot/papers/maxclique.ps" rel="nofollow noreferrer">Improved inapproximability results for maxclique, chromatic number and approximate graph coloring. </a> show that for all sufficiently large constants <span class="math-container">$k$</span> it is NP-hard to color a <span class="math-container">$k$</span>-colorable graph with <span class="math-container">$k^{\Omega(\log k)}$</span> colors</p>
</li>
<li><p>A very recent result of S. Huang <a href="http://arxiv.org/abs/1301.5216" rel="nofollow noreferrer">Improved Hardness of Approximating Chromatic Number</a> says that for all sufficiently large <span class="math-container">$k$</span>, it is NP-hard to color a <span class="math-container">$k$</span>-colorable graphs with <span class="math-container">$2^{k^{1/3}}$</span> colors.</p>
</li>
<li><p>If you are willing to assume Unique Games conjecture (in fact <span class="math-container">$d$</span>-to-1 conjecture), then I. Dinur, E. Mossel and O. Regev show in <a href="http://www.wisdom.weizmann.ac.il/%7Edinuri/mypapers/DMR.pdf" rel="nofollow noreferrer">Conditional Hardness for Approximate Coloring</a> that for any <span class="math-container">$K$</span> it is hard to color 4-colorable graphs with <span class="math-container">$K$</span> colors.</p>
</li>
<li><p>A follow-up result of I. Dinur and I.Shinkar <a href="https://sites.google.com/site/igorshinkar/quantDMR.pdf" rel="nofollow noreferrer">On the Conditional Hardness of Coloring a 4-Colorable Graph with Super-Constant Number of Colors</a> shows that under some stronger assumptions on the hardness of Unique Games it is hard to color 4-colorable graphs with <span class="math-container">$\log(n)^{0.001}$</span> colors, where <span class="math-container">$n$</span> is the number of vertices in the graph.</p>
</li>
</ul>

CC BY-SA 3.0
2014-02-21T04:00:34.813Z
The last result is interesting, but is there a decimal point mishap there? Two zeros before the decimal is odd...
Jeremy Kun
CC BY-SA 4.0
2013-08-15T03:46:18.197Z
2021-07-12T07:42:16.143Z
2021-07-12T07:42:16.143Z
Igor Shinkar
<p>Here are the references:</p>

<ul>
<li>S. Khanna, N. Linial, and S. Safra, <a href="http://link.springer.com/article/10.1007/s004930070013">On the hardness of approximating the chromatic number,
Combinatoria, 20 (2000), pp. 393–415.</a></li>
<li>C. Lund and M. Yannakakis, <a href="http://dl.acm.org/citation.cfm?id=306789&amp;CFID=239309170&amp;CFTOKEN=77596634">On the hardness of approximating minimization problems, J.
ACM, 41 (1994), pp. 960–981.</a></li>
</ul>

CC BY-SA 3.0
2013-08-14T21:53:43.737Z
2013-08-14T22:13:01.280Z
2013-08-14T22:13:01.280Z
vb le
<p>I heard of a result in approximate graph coloring, but cannot find the source. The result is:</p>

<p>For every constant $h$ there exists a sufficiently large $k$ such that coloring a $k$-colorable graph with $hk$ colors is NP-hard.</p>

<p>Could someone please point me to the relevant paper?</p>

<reference-request><approximation-hardness><graph-colouring>
Reference Request: Asymptotic hardness of $hk$ coloring $k$-colorable graphs
Jeremy Kun
# Reference Request: Asymptotic hardness of $hk$ coloring $k$-colorable graphs

(Asked by: username_0 on 2013-08-14)

I heard of a result in approximate graph coloring, but cannot find the source. The result is:

For every constant $h$ there exists a sufficiently large $k$ such that coloring a $k$-colorable graph with $hk$ colors is NP-hard.

Could someone please point me to the relevant paper?

**Tags:** reference-request, approximation-hardness, graph-colouring


---

## 2 answers

### Answer by username_2 on 2013-08-14. Score: 12 | Accepted answer

Here are the references:

* S. Khanna, N. Linial, and S. Safra, [On the hardness of approximating the chromatic number,
  Combinatoria, 20 (2000), pp. 393–415.](http://link.springer.com/article/10.1007/s004930070013)
* C. Lund and M. Yannakakis, [On the hardness of approximating minimization problems, J.
  ACM, 41 (1994), pp. 960–981.](http://dl.acm.org/citation.cfm?id=306789&CFID=239309170&CFTOKEN=77596634)


---

### Answer by username_1 on 2013-08-15. Score: 12

There are much stronger results for approximate graph coloring.

* S. Khot, [Improved inapproximability results for maxclique, chromatic number and approximate graph coloring.](http://www.cs.nyu.edu/%7Ekhot/papers/maxclique.ps)  show that for all sufficiently large constants $k$ it is NP-hard to color a $k$-colorable graph with $k^{\Omega(\log k)}$ colors
* A very recent result of S. Huang [Improved Hardness of Approximating Chromatic Number](http://arxiv.org/abs/1301.5216) says that for all sufficiently large $k$, it is NP-hard to color a $k$-colorable graphs with $2^{k^{1/3}}$ colors.
* If you are willing to assume Unique Games conjecture (in fact $d$-to-1 conjecture), then I. Dinur, E. Mossel and O. Regev show in [Conditional Hardness for Approximate Coloring](http://www.wisdom.weizmann.ac.il/%7Edinuri/mypapers/DMR.pdf) that for any $K$ it is hard to color 4-colorable graphs with $K$ colors.
* A follow-up result of I. Dinur and I.Shinkar [On the Conditional Hardness of Coloring a 4-Colorable Graph with Super-Constant Number of Colors](https://sites.google.com/site/igorshinkar/quantDMR.pdf) shows that under some stronger assumptions on the hardness of Unique Games it is hard to color 4-colorable graphs with $\log(n)^{0.001}$ colors, where $n$ is the number of vertices in the graph.

> **Comments:**
> **username_0**: The last result is interesting, but is there a decimal point mishap there? Two zeros before the decimal is odd...  

---

