The black-and-white coloring problem on trees Academic Article uri icon


  • 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.

publication date

  • January 1, 2009