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


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.


Roland Schmid
PhD student


	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 = {},
	archivePrefix = {arXiv},
	eprint = {2108.03882}

DOI: 10.48550/arXiv.2108.03882