Odniesienie Zapytanie: Asymptotic twardość farbowanie -colorable wykresach

Słyszałem o przybliżonym zabarwieniu wykresu, ale nie mogę znaleźć źródła. Wynik to:

Dla każdego stałego istnieje wystarczająco duża taki sposób, że barwienia -colorable wykres z kolorów NP-trudne.$h$$k$$k$$hk$

Czy ktoś mógłby mi wskazać odpowiedni artykuł?

Oto referencje:

• S. Khanna, N. Linial i S. Safra, O twardości aproksymacji liczby chromatycznej, Combinatoria, 20 (2000), s. 393–415.
• C. Lund i M. Yannakakis, O twardości przybliżania problemów minimalizacji, J. ACM, 41 (1994), s. 960–981.

Istnieją znacznie silniejsze wyniki dla przybliżonego kolorowania wykresów.

• S. Khot, Poprawione wyniki niedopuszczalności dla maksimum, liczby chromatycznej i przybliżonego zabarwienia wykresu. pokazują, że dla wszystkich dostatecznie dużych stałych to jest NP-trudne do koloru a -colorable wykresu z kolory$k$$k$$k^{\Omega(log k)}$

• Niedawny wynik ulepszonej twardości aproksymowanej liczby chromatycznej S. Huanga mówi, że dla wszystkich wystarczająco dużych wartości trudno jest pokolorować grafikami w kolorze pomocą kolorów .$k$$k$$2^{k^{1/3}}$

• Jeśli chcesz założyć hipotezę o unikalnych grach (w rzeczywistości domysł -do-1), wówczas I. Dinur, E. Mossel i O. Regev pokazują w Warunkowej twardości dla przybliżonego zabarwienia, że dla każdego trudno jest pokolorować 4- kolorowe wykresy z kolorami$d$$K$$K$

• Kolejny wynik I. Dinura i I. Shinkara na temat warunkowej twardości barwienia 4-kolorowalnego wykresu z super-stałą liczbą kolorów pokazuje, że przy pewnych mocniejszych założeniach dotyczących twardości unikalnych gier trudno jest pokolorować 4 kolorowe wykresy z kolorów, gdzie jest liczbą wierzchołków na wykresie.$\log(n)^{0.001}$$n$