Two-Class (r,k)-Coloring: Coloring with Service Guarantees

Abstract

This paper introduces the Two-Class ($r$,$k$)-Coloring problem: Given a fixed number of $k$ colors, such that only $r$ of these $k$ colors allow conflicts, what is the minimal number of conflicts incurred by an optimal coloring of the graph? We establish that the family of Two-Class ($r$,$k$)-Coloring problems is NP-complete for any $k\ge 2$ when $(r,k)\ne (0,2)$. Furthermore, we show that Two-Class ($r$,$k$)-Coloring for $k\ge 2$ colors with one ($r=1$) relaxed color cannot be approximated to any constant factor ($\notin$ APX). Finally, we show that Two-Class ($r$,$k$)-Coloring with $k\ge r\ge 2$ colors is APX-complete.

13 pages, 4 figures