Reference for NP-hardness of 3-colouring?
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.