# MPI-I-98-1-005

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

### Jansen, Klaus

**MPI-I-98-1-005**. January** **1998, 12 pages. | Status:** **available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:

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

Acknowledgement:** **

References to related material:

To download this research report, please select the type of document that fits best your needs. | Attachement Size(s): |

| 130 KBytes |

Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView |

**URL to this document: **http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1998-1-005

**BibTeX**
`@TECHREPORT{``Jansen98-1-005``,`

` AUTHOR = {Jansen, Klaus},`

` TITLE = {The mutual exclusion scheduling problem for permutation and comparability graphs},`

` TYPE = {Research Report},`

` INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},`

` ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},`

` NUMBER = {MPI-I-98-1-005},`

` MONTH = {January},`

` YEAR = {1998},`

` ISSN = {0946-011X},`

`}`