Key points are not available for this paper at this time.
The problem of computing the chromatic number of a graph is considered. No known approximation algorithm can guarantee a better than O(n/sup 0.4/) coloring on a three-chromatic graph with n vertices. Evidence is provided that it is inherently impossible to achieve a better than n/sup epsilon / ratio in polynomial time by showing that 'breaking the n/sup epsilon / barrier' will automatically lead to vastly better polynomial-time approximation algorithms that achieve ratios closer to log n.>
Linial et al. (Sun,) studied this question.