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. Jul 25, 2013 at 20:05

2 Answers

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

Update: see comments below.

• If I am not mistaken, Stockmeyer did not prove the NP-hardness of 3-Colouring in that paper. There, he reduces 3-Colouring to Planar 3-Colouring and refer hardness of 3-Colouring to Karp (1972). This is wrong as pointed out by Thore Husfeldt. Apr 27, 2013 at 8:06
• I see. Thanks user13136! Unfortunately, I don't have access to this paper now. I saw only the abstract of this paper and references to it.
– Yury
Apr 27, 2013 at 13:49
• I have now seen Stockmeyer’s paper via the ACM digital library, and it does include a full proof of the hardness of 3-colorability. (Reduction from 3-Satisfiability.) Thus it seems as if Yury’s initial statement is correct after all, and Stockmeyer and Lovász obtained the result independently (and using different reductions.) Apr 29, 2013 at 11:52
• Ouch! I was not aware that only one checkmark can be assigned. The Stockmeyer answer is correct, so I mechanically clicked the checkmark. What should I do, torn as I am between two mutually exclusive versions of the truth? Apr 29, 2013 at 17:21
• Oh, I was just curious because I find the paper of Lovasz quite pretty. I didn't want to depreciate Yury's answer neither think vb le is very heartbroken about it;) Apr 29, 2013 at 18:26