We know that the chromatic number of a graph $G$ is the smallest number of colors needed to color the vertices of $G$ so that no two adjacent vertices share the same color .

But why the coloring is NP-HARD ? and what is the difference between it and vertex coloring ? enter image description here

  • 4
    $\begingroup$ Do you know what NP-Hard means in terms of theoretical computer science ? It essentially means that any problem in NP can be transformed so it becomes the problem of finding the chromatic number of a graph. And can you define vertex coloring ? As far as I know, it's the same thing. $\endgroup$ – Manuel Lafond Jul 8 '15 at 14:59
  • $\begingroup$ Yes, I know, but why this problem 'Chromatic Coloring' is NP-Hard ? $\endgroup$ – Mike Bluer Jul 8 '15 at 15:02
  • 2
    $\begingroup$ Even determining whether the chromatic number is $\le 3$ (that is, whether a given graph is 3-colorable) is NP-hard. You can find several descriptions of the standard reduction from CNF-SAT by googling for 3-coloring np-hard. $\endgroup$ – Henning Makholm Jul 8 '15 at 15:07
  • 2
    $\begingroup$ One reason is that the number of colorings we have to try grows very very fast and we don't have a clear way of deciding which colorings are "worth trying". $\endgroup$ – Jorge Fernández Hidalgo Jul 8 '15 at 15:08
  • $\begingroup$ @Henning Makholm why it is NP-Hard not NP-Complete, I think it is NP-COMPLETE $\endgroup$ – Tandee Holwa Jul 9 '15 at 23:22

A decision problem A is NP-hard means that if you can solve A in polynomial in input size, you can solve any NP problem in polynomial time (in input size). The mechanism to convert a problem B to a problem A (in polynomial time) is called a reduction from B to A.

Input: A graph G
Question: Is G 3-colourable (i.e., is $\chi(G)\leq 3)$ ?

The problem 3-COLOURABILITY is NP-hard because there is a polynomial time reduction from 3-SAT to 3-COLOURABILITY and there is a reduction from SAT to 3-SAT. It is proven that if you can solve SAT in polynomial time, you can solve any NP problem in polynomial time (Cook's theorem). Hence, checking if chromatic number is at most 3 is hard and therefore finding chromatic number exactly must be hard as well.

Note: (Read this in case you get interested in reductions)
You can find a reduction from NAE SAT to 3-COLOURABILITY more easily (i think so).

  • $\begingroup$ The first sentence of this is often found in popular treatments, but is slightly incorrect. As written it would be satisfied by any problem outside P, but if P≠NP then there exist NP-intermediate problems, which by definition are neither in P nor NP-hard. Instead, NP-hardness is defined explicitly by the existence of (poly-time many-one) reductions. $\endgroup$ – Henning Makholm Sep 7 '18 at 5:29

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.