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 GG and an integer kk, the problem is to find a minimum coloring of GG such that each color is used at most kk 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 NPNP-hard for interval graphs, even if kk 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 NPNP-hardness result of Bodlaender and Jansen, we obtain a more precise cartography of the complexity of the problem for the classes of graphs studied.