On the complexity of the black-and-white coloring problem on some classes of perfect graphs ?
Given a graph G and integers b and w. The black-and-white coloring problem asks if there exist disjoint sets of vertices B and W  with |B|=b | B | = b and |W|=w | W | = w such that no vertex in B is adjacent to any vertex in W. In this paper we show that the problem is polynomial when restricted to cographs, interval graphs, permutation graphs, distance-hereditary graphs, and strongly chordal graphs. We show that the problem is NP-complete on splitgraphs.
black-and-white coloring cographs interval graphs distance-hereditary graphs strongly chordal graphs threshold graphs