Minimal colouring problem aproximation threshold Given that 3-colouring and 4-colouring are NP-complete show that the
  aproximation threshold of the minimal colouring problem is greater or
  equal than $\frac{4}{3}$.


My current approach is to work by contradiction assuming there was such an algorithm that in polynomial time can produce a $\delta$-aproximation with $\delta &lt; \frac{4}{3}$ using the fact that 3-colouring and 4-colouring are NP-complete. I didn't obtain much progress.

References

I just wanted to point out that this is an application of the "Gap technique" presented in the book "Complexity and Aproximation" of Auseillo et alii., I wasn't familiar with the notation they use so I couldn't understand how to fully apply the technique.
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).