3个可着色性问题的近似硬度

Question

如果我们有多项式算法，即$ c $ -approximation，$ c < frac {4} {3} $对于图形，它们的色数$ geq k $ the $ np = p $，如何证明此类语句？

我也对此语句有某种解释：当$ c < frac {4} {3} {3} quad 时forall k geq 3 $

Answer 1

提示：考虑平面图。