Mutual exclusion scheduling with interval graphs or related classes, Part I

In this paper, the mutual exclusion scheduling problem is addressed. Given a simple and undirected graph G and an integer k, the problem is to find a minimum coloring of G such that each color is used at most k times. When restricted to interval graphs or related classes like circular-arc graphs and tolerance graphs, the problem has some applications in workforce planning. Unfortunately, the problem is shown to be NP-hard for interval graphs, even if k is a constant greater than or equal to four H.L. Bodlaender and K. Jansen Restrictions of graph partition problems. Part I, Theoretical Computer Science 148(1995) pp. 93-109]. Several polynomial-time solvable cases significant in practice are exhibited here, for which we took care to devise simple and efficient algorithms (in particular linear-time and space algorithms). On the other hand, by reinforcing the NP-hardness result of Bodlaender and Jansen, we obtain a more precise cartography of the complexity of the problem for the classes of graphs studied.