# Why finding chromatic number is NP-Hard?

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 ?

• 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. Jul 8, 2015 at 14:59
• Yes, I know, but why this problem 'Chromatic Coloring' is NP-Hard ? Jul 8, 2015 at 15:02
• 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. Jul 8, 2015 at 15:07
• 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". Jul 8, 2015 at 15:08
• @Henning Makholm why it is NP-Hard not NP-Complete, I think it is NP-COMPLETE Jul 9, 2015 at 23:22

## 1 Answer

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

• 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. Sep 7, 2018 at 5:29