# 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 < \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.

## 1 Answer

Consider 3-coloring and suppose that a $\delta$-approximation algorithm $A$ for the minimum coloring problem with $\delta < \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).