The black-and-white coloring problem on circle 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 and |W|=w such that no two vertices x in B and y in W are adjacent. In this paper we show that the problem is polynomial when restricted to permutation graphs and, more generally, to circle graphs. 
Ton Kloks, Sheung-Hung Poon and Yue-Li Wang
cs.DM