Cheap and Secure Web Hosting Provider : See Now

# [Solved]: Hardness of approximation of the 3 colorability problem

, ,
Problem Detail:

If we have polynomial algorithm that $c$-approximation, $c<\frac{4}{3}$ for graphs that their chromatic number $\geq k$ then $NP=P$, how to prove such statements?

I also have some sort of explanation of this statement: It's NP-hard to separate between graphs that have chromatic number $k$ and chromatic number $c \cdot k$ when $c<\frac{4}{3} \quad \forall k\geq 3$

#### Answered By : Yuval Filmus

Hint: Consider planar graphs.