Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
438301 | Theoretical Computer Science | 2014 | 13 Pages |
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|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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Ton Kloks, Sheung-Hung Poon, Feng-Ren Tsai, Yue-Li Wang,