About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
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.