Twardość przybliżonej ułamkowej liczby chromatycznej na wykresach ze stopniem granicznym

Czy trudno jest apx-przybliżać ułamkową liczbę chromatyczną na wykresach ze stopniem granicznym?

Tak.

Jeśli dobrze zrozumiałem, dowód Twierdzenia 1.6 w Khot (2001) stwierdza, że ​​trudno jest rozróżnić następujące dwa przypadki, nawet jeśli skupimy się na grafach stopnia ograniczonego o wystarczająco wysokim stopniu:

1. Jest kolorowanie.$k$
2. Stosunek liczby wierzchołków do maksymalnego rozmiaru niezależnego zestawu wynosi co najmniej .$k^{\log(k)/25}$

Z perspektywy ułamkowej liczby chromatycznej te dwa przypadki to:

1. Ułamkowa liczba chromatyczna wynosi co najwyżej .$k$
2. Ułamkowa liczba chromatyczna wynosi co najmniej .$k^{\log(k)/25}$

Teraz musimy pamiętać, że potrzebujemy wystarczająco wysokich stopni (w funkcji ). Ale o ile widzę, dowód ma np. Następującą dogodną następstwo, która może być już wystarczająca dla twoich celów:$k$

• Biorąc pod uwagę dowolną stałą , istnieje stałe i tak, że po problem NP-trudny: podany wykres maksymalnego stopnia zdecydować, czy ułamkowe liczby chromatycznych wynosi co najwyżej lub co najmniej .$\alpha$$\Delta$$c$$G$$\Delta$$G$$c$$\alpha c$

Oczywiście oznacza to już, że nie ma PTAS, chyba że P = NP.