Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
DOI: 10.7155/jgaa.00258 The Black-and-White Coloring Problem on Chordal Graphs Shira Zucker Vol. 16, no. 2, pp. 261-281, 2012. 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. This problem is known to be NP-complete in general. We provide here a polynomial time algorithm for chordal graphs.
|
Revised: May 2011. Published: March 2012. Final: March 2012. Submitted: September 2009. Reviewed: January 2011. Revised: September 2011. Reviewed: August 2011. Accepted: February 2012. Communicated by Martin Fürer |
Journal of Graph Algorithms and Applications |