MINIMUM GRAPH COLORING problem

MINIMUM GRAPH COLORING problem --- задача о минимальной раскраске графа.

The MINIMUM GRAPH COLORING problem (or MGCP) consists in finding a coloring with the smallest number of colors. This problem is known to be NP-hard, approximable within factor [math]\displaystyle{ {\mathcal O}(|V|(\log \log |V|)^{2}/(\log |V|)^{3}) }[/math] and not approximable within factor [math]\displaystyle{ |V|^{1-\epsilon} }[/math] for any [math]\displaystyle{ \epsilon \gt 0 }[/math].