For $3 \leq q < Q$ we consider the $\text{ApproxColoring}(q,Q)$ problem of deciding for a given graph $G$ whether $\chi(G) \leq q$ or $\chi(G) \geq Q$. It was show in [DMR06] that the problem $\text{ApproxColoring}(q,Q)$ is NP-hard for $q=3,4$ and arbitrary large constant $Q$ under variants of the Unique Games Conjecture.

In this paper we give a tighter analysis of the reduction of [DMR06] from Unique Games to the $\text{ApproxColoring}$ problem. We find that (under appropriate conjecture) a careful calculation of the parameters in [DMR06] implies hardness of coloring a 4-colorable graph with $\log^c(\log(n))$ colors for some positive constant $c$. By improving the analysis of the reduction we show hardness of coloring a 4-colorable graph with $\log^c(n)$ colors for some positive constant $c$.

The main technical contribution of the paper is a variant of the Majority is Stablest Theorem, which says that among all balanced functions in which every coordinate has $o(1)$ influence, the Majority function has the largest noise stability. We adapt the theorem for our applications to get a better dependency between the parameters required for the reduction.