Three-quarter approximation for the number of unused colors in graph coloring

Abstract

The graph coloring problem is to color vertices of a graph so that no adjacent vertices are of the same color. The problem is difficult not only in finding the optimal solution, but also in approximation. Since it is hard to approximate the minimum number of colors, we consider to approximate the maximum number of unused colors. This approximation is based on saving colors with respect to the most naive coloring method, which colors each vertex with a different color. In this paper we propose a polynomial-time graph coloring algorithm with approximation ratio 3/4 for the maximum number of unused colors, which improves the previous result 2/3. (C) 1999 Elsevier Science Inc. All rights reserved.