Referenzanfrage: Asymptotische Härte von

Ich habe von einem Ergebnis mit ungefährer Grafikfarbe gehört, kann aber die Quelle nicht finden. Das Ergebnis ist:

Für jede Konstante existiert ein ausreichend großes k, so dass das Färben eines k- färbbaren Graphen mit h k- Farben NP-hart ist.$h$$k$$k$$hk$

Könnte mich bitte jemand auf das entsprechende Papier verweisen?

Hier sind die Referenzen:

• S. Khanna, N. Linial und S. Safra, Zur Kombinationshärte der chromatischen Zahl, Combinatoria, 20 (2000), S. 393–415.
• C. Lund und M. Yannakakis, Zur Härte der Approximation von Minimierungsproblemen, J. ACM, 41 (1994), S. 960–981.

Es gibt viel stärkere Ergebnisse für die ungefähre Grafikfärbung.

• $k$$k$$k^{\Omega(log k)}$

• $k$$k$$2^{k^{1/3}}$

• $d$$K$$K$

• $\log(n)^{0.001}$$n$