Kekerasan mendekati angka kromatik fraksional pada grafik derajat terbatas

Apakah sulit untuk memperkirakan angka kromatik fraksional pada grafik derajat terbatas?

Iya.

Jika saya mengerti dengan benar, bukti Teorema 1.6 dalam Khot (2001) menetapkan bahwa NP-sulit untuk membedakan antara dua kasus berikut, bahkan jika kita fokus pada grafik tingkat-terikat dari tingkat yang cukup tinggi:

1. Ada warna- .$k$
2. Rasio jumlah simpul dengan ukuran maksimum dari set independen adalah setidaknya .$k^{\log(k)/25}$

Dari perspektif bilangan kromatik fraksional, kedua kasus ini adalah:

1. Jumlah kromatik fraksional paling banyak .$k$
2. Angka kromatik fraksional setidaknya adalah .$k^{\log(k)/25}$

Sekarang kita harus ingat bahwa kita membutuhkan derajat yang cukup tinggi (sebagai fungsi dari ). Tetapi sejauh yang saya bisa lihat, buktinya memiliki, misalnya, akibat wajar nyaman berikut yang mungkin sudah cukup untuk tujuan Anda:$k$

• Diberikan konstanta , ada konstanta Δ dan c sehingga masalah berikut dalam NP-hard: diberi grafik G dengan derajat maksimum Δ , putuskan apakah angka kromatik fraksional G paling banyak c atau setidaknya α c .$\alpha$$\Delta$$c$$G$$\Delta$$G$$c$$\alpha c$

Tentu saja ini sudah menyiratkan bahwa tidak ada PTAS, kecuali P = NP.