RESTRICTIONS OF GRAPH PARTITION PROBLEMS .1.

In this paper partition problems into k independent sets or cliques of bounded size k' are analyzed for several classes of graphs. We prove the computational complexity of both problems restricted to cographs, split graphs, bipartite graphs and interval graphs given general or co nstant k and k'. It is shown, that the assignment problem for operatio ns in a branching flow graph to processors, each with a limit on the n umber of executable operations, equals the first problem restricted to cographs. In addition a job-assignment problem given intervals for ea ch job and k machines, each executing at most k' jobs, equals the firs t problem restricted to interval graphs. It is shown, that both proble m are NP-complete.