DIMACS TR: 98-08
The Mutual Exclusion Scheduling Problem for Permutation
and Comparability Graphs
Author: Klaus Jansen
In this paper, we consider the mutual exclusion scheduling problem
for comparability graphs.
Given an undirected graph $G$ and a fixed constant $m$, the problem is
to find a minimum coloring of $G$ such that each color is used at most
$m$ times. The complexity of this problem for comparability graphs was
mentioned as an open problem by M\"ohring (1985) and for permutation
graphs (a subclass of comparability graphs) as an open problem by Lonc
(1991). We prove that this problem is already NP-complete for permutation
graphs and for each fixed constant $m \ge 6$.
Paper Available at:
DIMACS Home Page