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.


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.