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. – Manuel Lafond Jul 8 '15 at 14:59
• Yes, I know, but why this problem 'Chromatic Coloring' is NP-Hard ? – Mike Bluer Jul 8 '15 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. – Henning Makholm Jul 8 '15 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". – Jorge Fernández Hidalgo Jul 8 '15 at 15:08
• @Henning Makholm why it is NP-Hard not NP-Complete, I think it is NP-COMPLETE – Tandee Holwa Jul 9 '15 at 23:22

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