Abstract
The problem of computing the chromatic number of a graph is considered. No known approximation algorithm can guarantee a better than O(n0.4) coloring on a three-chromatic graph with n vertices. Evidence is provided that it is inherently impossible to achieve a better than nε ratio in polynomial time by showing that 'breaking the nε barrier' will automatically lead to vastly better polynomial-time approximation algorithms that achieve ratios closer to log n.