0
$\begingroup$

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

$\endgroup$
8
  • 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$ Jul 8, 2015 at 14:59
  • $\begingroup$ Yes, I know, but why this problem 'Chromatic Coloring' is NP-Hard ? $\endgroup$
    – Mike Bluer
    Jul 8, 2015 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$ Jul 8, 2015 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$
    – Asinomás
    Jul 8, 2015 at 15:08
  • $\begingroup$ @Henning Makholm why it is NP-Hard not NP-Complete, I think it is NP-COMPLETE $\endgroup$ Jul 9, 2015 at 23:22

1 Answer 1

1
$\begingroup$

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.

3-COLOURABILITY
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).

$\endgroup$
1
  • $\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$ Sep 7, 2018 at 5:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .