The Black-and-White Coloring Problem on Trees
Daniel Berend, Shira Zucker · Journal of Graph Algorithms and Applications · 2009
Given a graph G and positive integers b and w, the black-and-white coloring problem asks about the existence of a partial vertex-coloring of G, with b vertices colored black and w white, such that there is no edge between a black and a white vertex. We suggest an improved algorithm for solving this problem on trees.