Hardness of approximation of the 3 colorability problem
-
16-10-2019 - |
Question
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$
Solution
Hint: Consider planar graphs.
Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange