Approximation results for the minimum graph coloring problem (Q1321829)

We devise a new polynomial time approximation algorithm for the minimum vertex coloring problem. We analyze the approximation performance of this algorithm by using a new approximation measure, namely the ratio \([\omega(I) - \lambda(I)]/[\omega(I) - \beta(I)]\), called differential approximation ratio, where, for an instance \(I\), \(\omega(I)\) (resp. \(\lambda(I)\), \(\beta(I)\)) is the cardinality of the worst case (resp. approximated, optimal) solution of an instance \(I\) of the problem. We prove that the differential approximation ratio of the minimum vertex coloring problem is bounded below by 1/2 (in the framework of the classical approximation theory, vertex coloring is not constant- approximable). We also prove that this bound is tight for the algorithm. We show that the problem does not admit differential polynomial time approximation schema. Finally, we devise differential-ratio-preserving reductions linking vertex coloring to vertex covering by cliques and edge covering by cliques problems. A consequence of these reductions is that the differential approximation ratio for vertex coloring is transferred to the latter problems.