34

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

vb le
  • 4,828
  • 1
  • 37
  • 46
Thore Husfeldt
  • 780
  • 6
  • 11
  • 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

2 Answers2

44

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.

vb le
  • 4,828
  • 1
  • 37
  • 46
20

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.

Yury
  • 3,899
  • 23
  • 29
  • 6
    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. – user13136 Apr 27 '13 at 08:06
  • 2
    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 '13 at 13:49
  • 4
    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.) – Thore Husfeldt Apr 29 '13 at 11:52
  • Ah,my mistake: I only read the first three pages, and he gave the reduction from 3-SAT to 3-COLOURING at the end of that paper, after his reduction 3-COLOURING to PLANAR 3-COLOURING. Thank you for pointing out! But what is wrong with Lovasz's proof (so that you changed your accepting)? – user13136 Apr 29 '13 at 15:09
  • 3
    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? – Thore Husfeldt Apr 29 '13 at 17:21
  • 1
    My answer only complements the answer of vb le. Accept his answer. – Yury Apr 29 '13 at 17:57
  • 2
    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;) – user13136 Apr 29 '13 at 18:26
  • 2
    @Thore Husfeldt Don't worry, it happens to all of us ;-)) – vb le Apr 29 '13 at 18:43