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