Referência para dureza NP de 3 cores?

Eu tenho uma pergunta histórica.

Estou tentando determinar a referência para o fato de que 3 cores de gráficos (alternativamente, cores para determinado ) são difíceis de NP.k ≥ $k$$k\geq 3$

A resposta tentadora é o "artigo original de Karp", mas isso está errado. Aqui está uma varredura: Redutibilidade entre problemas combinatórios, Karp (1972) . Isso prova que o número cromático (entrada: um gráfico. Saída: ) é difícil. Esse é um problema mais difícil, e a redução é diferente da construção padrão do gadget (com 3 cores, True, False e Ground) que implica em dureza de 3 cores.$\chi(G)$

Garey e Johnson, Computadores e intratabilidade , têm capacidade de como [GT4] e se referem a Karp (1972).$k$

László Lovász , Coberturas e coloração de hipergrafos , Anais da Quarta Conferência Sudeste de Combinatória, Teoria dos Gráficos e Computação, Utilitas Math., Winitas, Mann., 1973, pp. 3--12, provou que o número cromático se reduz a 3 colorabilidade.

Penso que essa é a primeira prova da NP-completude da 3-colourability.

Aqui está o artigo de Lovász; veja também a excelente explicação de Vašek Chvátal para a redução de Lovász.

Aqui está outro artigo de 1973 que prova que a 3 cores é NP-difícil.

Larry J. Stockmeyer. “A coloração plana 3 é polinomial completa.” ACM SIGACT News, vol. 5, n. 3, 1973.

(Parece que Lovász e Stockmeyer obtiveram seus resultados independentemente.)

Atualização: veja os comentários abaixo.