# Reference for NP-hardness of 3-colouring?

I have a historical question.

I’m trying to determine the reference for the fact that 3-colourability of graphs (alternatively, $k$-colourability for given $k\geq 3$) is NP-hard.

The tempting answer is “Karp’s original paper”, but that is wrong. Here’s a scan: Reducibility among Combinatorial Problems, Karp (1972). It proves that Chromatic number (Input: a graph. Output: $\chi(G)$) is hard. That’s a harder problem, and the reduction is different from the standard gadget construction (with 3 colours, True, False, and Ground) that implies hardness of 3-colourability.

Garey and Johnson, Computers and intractability, have $k$-colourability as [GT4] and refer to Karp (1972).

• On page 84, Garey and Johnson claim that 3-colorability is NP-complete by citing the Stockmeyer paper provided in Yury's answer. In Theorem 4.2, they also provide a simpler proof of Stockmeyer's result. – Tyson Williams Jul 25 '13 at 20:05

László Lovász, Coverings and coloring of hypergraphs, Proceedings of the Fourth Southeastern Conference on Combinatorics, Graph Theory, and Computing, Utilitas Math., Winnipeg, Man., 1973, pp. 3--12, proved that Chromatic number reduces to 3-colourability.

I think, that is the first proof for NP-completeness of 3-colourability.

Here is Lovász's paper; see also Vašek Chvátal's excellent explanation to Lovász's reduction.

Here is another paper from 1973 that proves that 3-colorability is NP-hard.

Larry J. Stockmeyer. “Planar 3-colorability is polynomial complete.” ACM SIGACT News, vol. 5, no. 3, 1973.

(It seems that Lovász and Stockmeyer obtained their results independently.)