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.
展开▼
