Odniesienie do twardości NP 3-zabarwienia?

Mam pytanie historyczne.

Próbuję ustalić odniesienie dla faktu, że 3-kolorowalność grafów (alternatywnie, kolorowalność dla danego k ≥ 3 ) jest NP-trudna.$k$$k\geq 3$

Kuszącą odpowiedzią jest „oryginał Karpa”, ale to nieprawda. Oto skan: Reducibility Among Combinatorial Problems, Karp (1972) . Dowodzi to, że liczba chromatyczna (Wejście: wykres. Wyjście: ) jest trudne. To trudniejszy problem, a redukcja różni się od standardowej konstrukcji gadżetu (z 3 kolorami, True, False i Ground), co oznacza twardość 3-kolorowalności.$\chi(G)$

Garey i Johnson, Computers and inctractability , mają kolorowalność jako [GT4] i odnoszą się do Karp (1972).$k$

László Lovász , Pokrycia i zabarwienie hipergraphów , Materiały z IV Konferencji Południowo-Wschodniej na temat kombinatoryki, Teorii Grafów i Informatyki, Utilitas Math., Winnipeg, Man., 1973, s. 3--12, udowodniły, że liczba Chromatyczna zmniejsza się do 3 kolorowalność.

Myślę, że to pierwszy dowód na kompletność NP 3-kolorowalności.

Oto praca Lovásza; zobacz także doskonałe wyjaśnienie Vaška Chvátala na temat obniżki Lovásza.

Oto kolejny papier z 1973 r., Który dowodzi, że 3-kolorowalność jest trudna do NP.

Larry J. Stockmeyer. „Planarna 3-kolorowalność jest zakończona wielomianem.” ACM SIGACT News, vol. 5, nr 3, 1973.

(Wygląda na to, że Lovász i Stockmeyer uzyskali swoje wyniki niezależnie).

Aktualizacja: patrz komentarze poniżej.