Referenz für die NP-Härte von 3-Farben?

Ich habe eine historische Frage.

Ich versuche, die Referenz für die Tatsache zu bestimmen, dass die 3-Färbbarkeit von Graphen (alternativ Färbbarkeit für gegebenes ) NP-hart ist.$k$$k\geq 3$

Die verlockende Antwort lautet „Karps Originalpapier“, aber das ist falsch. Hier ist ein Scan: Reduzierbarkeit unter kombinatorischen Problemen, Karp (1972) . Dies beweist, dass die chromatische Zahl (Eingabe: ein Graph. Ausgabe: ) schwer ist. Das ist ein schwierigeres Problem, und die Reduzierung unterscheidet sich von der Standard-Gadget-Konstruktion (mit 3 Farben, True, False und Ground), die eine Härte mit 3 Farben impliziert.$\chi(G)$

Garey und Johnson, Computers and intractability , haben eine Färbbarkeit als [GT4] und verweisen auf Karp (1972).$k$

László Lovász , Coverings and Colouring of Hypergraphs , Proceedings of the Fourth Southeastern Conference on Combinatorics, Graph Theory, and Computing, Utilitas Math., Winnipeg, Man. Färbbarkeit.

Ich denke, das ist der erste Beweis für die NP-Vollständigkeit der 3-Färbbarkeit.

Hier ist Lovász Papier; siehe auch Vašek Chvátals ausgezeichnete Erklärung zu Lovász 'Reduktion.

Hier ist ein weiteres Papier von 1973, das beweist, dass die 3-Färbbarkeit NP-hart ist.

Larry J. Stockmeyer. "Planare 3-Färbbarkeit ist polynomisch vollständig." ACM SIGACT News, vol. 5, nein. 3, 1973.

(Es scheint, dass Lovász und Stockmeyer ihre Ergebnisse unabhängig voneinander erhalten haben.)

Update: siehe Kommentare unten.