# Reference Request: Asymptotic hardness of $hk$ coloring $k$-colorable graphs

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?

## 2 Answers

Here are the references:

There are much stronger results for approximate graph coloring.

• The last result is interesting, but is there a decimal point mishap there? Two zeros before the decimal is odd... – Jeremy Kun Feb 21 '14 at 4:00