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

Question

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?

Answer 1

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.
• C. Lund and M. Yannakakis, On the hardness of approximating minimization problems, J. ACM, 41 (1994), pp. 960–981.

Answer 2

There are much stronger results for approximate graph coloring.

• S. Khot, Improved inapproximability results for maxclique, chromatic number and approximate graph coloring. 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 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 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 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.