  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 \geq 2$ when $(r, k) \neq (0,2)$. Furthermore, we show
that Two-Class ($r$,$k$)-Coloring for $k \geq 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 \geq r \geq 2$
colors is APX-complete.
