The Black-and-White Coloring Problem on Trees
Daniel Berend and Shira Zucker
Vol. 13, no. 2, pp. 133-152, 2009. Regular paper.
Abstract 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.
Submitted: June 2008.
Reviewed: February 2009.
Revised: March 2009.
Accepted: March 2009.
Final: April 2009.
Published: June 2009.
Communicated by Henk Meijer
article (PDF)