In this paper, we consider the mutual exclusion scheduling problem for ocmparability graphs. Given an undrected 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 ocmplexity of this problem for comparablity graphs was mentioned as an open problem by Mohring (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-compelte for permutation graphs and for each fixed constant m greater that or equal to 6.
展开▼
