Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
DOI: 10.7155/jgaa.00180 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.
|
Accepted: March 2009. Revised: March 2009. Final: April 2009. Reviewed: February 2009. Submitted: June 2008. Published: June 2009. Communicated by Henk Meijer |
Journal of Graph Algorithms and Applications |