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

**Authors:**Pál András Papp, Roland Schmid, Valentin Stoppiello, and Roger Wattenhofer

arXiv CoRR 2021

## 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≥2$ when $(r,k)≠(0,2)$. Furthermore, we show that Two-Class $(r,k)$-Coloring for $k≥2$ colors with one ($r=1$) relaxed color cannot be approximated to any constant factor (∉ APX). Finally, we show that Two-Class $(r,k)$-Coloring with $k≥r≥2$ colors is APX-complete.

## People

Roland Schmid

PhD student

## BibTex

```
@article{twoclass-r-k-coloring-abs/2108.03882,
author = {Pal Andras Papp and Roland Schmid and Valentin Stoppiello and Roger Wattenhofer},
title = {Two-Class (r,k)-Coloring: Coloring with Service Guarantees},
journal = {CoRR},
volume = {abs/2108.03882},
year = {2021},
url = {https://arxiv.org/abs/2108.03882},
archivePrefix = {arXiv},
eprint = {2108.03882}
}
```