Minimal colouring problem aproximation threshold
Consider 3-coloring and suppose that a $\delta$-approximation algorithm $A$ for the minimum coloring problem with $\delta &lt; \frac{4}{3}$ exists. 

Let $G$ be the input graph and $x$ be the solution returned by $A$.


If $G$ is 3-colorable then $A$ would return $3$. 
In fact, $x \lt 4$ since $A$ would return a solution $x \lt \ ( 3\cdot \delta)=3* \frac{4}{3}=4$ by hypothesis.
If $G$ is not 3 colorable then $A$ would return $x \geq 4$ since $G$ needs at least $4$ colors.


Hence, with $A$ you would be able to determine whether $G$ is 3 colorable or not. 

But 3-Coloring is NP-Complete (contradiction).