The black-and-white coloring problem on permutation graphs

Ton Kloks

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 vertex in B is adjacent to any vertex in W. In this paper we show that the problem is polynomial when restricted to permutation graphs.

Knowledge Graph

arrow_drop_up

Comments

Sign up or login to leave a comment