The Complexity of Near-Optimal Graph Coloring

Graph coloring problems, in which one would like to color the vertices of a given graph with a small number of colors so that no two adjacent vertices receive the same color, arise in many applications, including various scheduling and partitioning problems. In this paper the complexity and performance of algorithms which construct such colorings are investigated. For a graph G , let χ( G ) denote the minimum possible number of colors required to color G and, for any graph coloring algorithm A , let A ( G ) denote the number of colors used by A when applied to G . Since the graph coloring problem is known to be “NP-complete,” it is considered unlikely that any efficient algorithm can guarantee A ( G ) = χ( G ) for all input graphs. In this paper it is proved that even coming close to khgr;( G ) with a fast algorithm is hard. Specifically, it is shown that if for some constant r < 2 and constant d there exists a polynomial-time algorithm A which guarantees A ( G ) ≤ r ·χ( G ) + d , then there also exists a polynomial-time algorithm A which guarantees A ( G ) = χ( G ).