La dureté de l'approximation du problème 3 colorabilité

Question

Si nous avons algorithme polynôme $ c -approximation $, $ c <\ frac {4} {3} $ pour les graphiques que leur nombre chromatique $ \ geq k $, alors $ NP = P $, comment prouver ces déclarations ?

J'ai aussi une sorte d'explication de cette déclaration: Il est NP-difficile de séparer entre les graphiques qui ont nombre chromatique $ k $ et nombre chromatique $ c \ cdot k $ lorsque $ c <\ frac {4} {3} \ quad \ forall k \ geq 3 $

Answer 1

Astuce:. Considérez les graphes planaires