34
$\begingroup$

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

Improve this question
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Tyson Williams
    Jul 25, 2013 at 20:05

2 Answers 2

Reset to default
44
$\begingroup$

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.

Improve this answer
$\endgroup$
20
$\begingroup$

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.

Improve this answer
$\endgroup$
8
  • 6
    $\begingroup$ 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. $\endgroup$
    – user13136
    Apr 27, 2013 at 8:06
  • 2
    $\begingroup$ 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. $\endgroup$
    – Yury
    Apr 27, 2013 at 13:49
  • 4
    $\begingroup$ 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.) $\endgroup$
    – Thore Husfeldt
    Apr 29, 2013 at 11:52
  • 3
    $\begingroup$ 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? $\endgroup$
    – Thore Husfeldt
    Apr 29, 2013 at 17:21
  • 2
    $\begingroup$ 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;) $\endgroup$
    – user13136
    Apr 29, 2013 at 18:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.