<p>Here is another paper from 1973 that proves that 3-colorability is NP-hard.</p>

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

<p>(It seems that Lovász and Stockmeyer obtained their results independently.)</p>

<p><strong>Update: see comments below.</strong></p>

CC BY-SA 3.0
2013-04-27T08:06:15.970Z
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
CC BY-SA 3.0
2013-04-27T13:49:59.267Z
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
CC BY-SA 3.0
2013-04-29T11:52:01.730Z
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
CC BY-SA 3.0
2013-04-29T15:09:31.027Z
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
CC BY-SA 3.0
2013-04-29T17:21:46.187Z
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
CC BY-SA 3.0
2013-04-29T17:57:39.620Z
My answer only complements the answer of vb le. Accept his answer.
Yury
CC BY-SA 3.0
2013-04-29T18:26:56.820Z
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
CC BY-SA 3.0
2013-04-29T18:43:02.570Z
@Thore Husfeldt Don't worry, it happens to all of us ;-))
vb le
CC BY-SA 3.0
2013-04-26T23:20:24.030Z
2013-04-29T14:23:18.893Z
2013-04-29T14:23:18.893Z
Yury
<p><strong>László Lovász</strong>, <em>Coverings and coloring of hypergraphs</em>, 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. </p>

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

<p><a href="http://www.cs.elte.hu/~lovasz/scans/covercolor.pdf">Here</a> is Lovász's paper; see also Vašek Chvátal's excellent <a href="http://users.encs.concordia.ca/~chvatal/notes/color.html">explanation</a> to Lovász's reduction.</p>

CC BY-SA 3.0
2013-04-25T11:13:16.677Z
2013-04-25T12:09:06.193Z
2013-04-25T12:09:06.193Z
vb le
<p>I have a historical question.</p>

<p>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.</p>

<p>The tempting answer is “Karp’s original paper”, but that is wrong. Here’s a scan: <a href="http://cgi.di.uoa.gr/~sgk/teaching/grad/handouts/karp.pdf">Reducibility among Combinatorial Problems, Karp (1972)</a>. 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.</p>

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

CC BY-SA 3.0
2013-07-25T20:05:52.727Z
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
<np-hardness><ho.history-overview>
Reference for NP-hardness of 3-colouring?
Thore Husfeldt
# Reference for NP-hardness of 3-colouring?

(Asked by: username_0 on 2013-04-25)

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)](http://cgi.di.uoa.gr/~sgk/teaching/grad/handouts/karp.pdf). 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).

**Tags:** np-hardness, ho.history-overview
> **Comments:**
> **username_1**: 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.  

---

## 2 answers

### Answer by username_4 on 2013-04-25. Score: 44 | Accepted answer

**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](http://www.cs.elte.hu/~lovasz/scans/covercolor.pdf) is Lovász's paper; see also Vašek Chvátal's excellent [explanation](http://users.encs.concordia.ca/~chvatal/notes/color.html) to Lovász's reduction.


---

### Answer by username_2 on 2013-04-26. Score: 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.**

> **Comments:**
> **username_3**: 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.  
> **username_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.  
> **username_0**: 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.)  
> **username_3**: 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)?  
> **username_0**: 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?  
> **username_2**: My answer only complements the answer of vb le. Accept his answer.  
> **username_3**: 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;)  
> **username_4**: @Thore Husfeldt Don't worry, it happens to all of us ;-))  

---

