Твердость приближения 3 проблемы с ореалом

Question

Если у нас есть полиномиальный алгоритм, который $ c $ -proximation, $ c < frac {4} {3} $ для графиков, которые их хроматическое число $ geq k $ then $ np = p $, как доказать такие утверждения?

У меня также есть какое-то объяснение этого утверждения: np-hard разделять между графиками, которые имеют хроматическое число $ k $ и хроматическое число $ c cdot k $, когда $ c < frac {4} {3} Quad forall K geq 3 $

Answer 1

Подсказка: рассмотрите планарные графики.