# Item

ITEM ACTIONSEXPORT

Released

Report

#### The mutual exclusion scheduling problem for permutation and comparability graphs

##### Fulltext (public)

MPI-I-98-1-005.pdf

(Any fulltext), 182KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Jansen, K.(1998). *The mutual exclusion scheduling problem for
permutation and comparability graphs* (MPI-I-1998-1-005). Saarbrücken: Max-Planck-Institut für Informatik.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-7BE5-E

##### Abstract

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$.