The black-and-white coloring problem on circle graphs

Abstract

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.

This paper has been withdrawn by the author due to a critical mistake in the circle graph algorithm