Splitting trees (Q1356762)

This paper considers the problem to find in a graph \(G=(V,E)\) a coloring of \(x\) vertices with the color white and \(y\) vertices with the color black, such that no white vertex is adjacent to a black vertex (and each vertex receives at most one color). Such a coloring is called a black-and-white coloring; \(x\) and \(y\) are given numbers. The paper considers the problem for trees. An \(O(n^3)\) algorithm for the problem is given, based on dynamic programming. With the help of two new notions, the splitting number, and the connected splitting number, necessary conditions for the existence of a black-and-white coloring with the desired number of black and white vertices are obtained. The conditions can be checked in \(O(n \log n)\), and \(O(n)\) time, respectively; if one of them holds, the desired black-and-white coloring can be made in linear time. The splitting number is the minimum number of successive forest splittings which lead to the deletion of all edges of the tree, where a forest splitting consists of taking a chain in each of the non-trivial trees in the forest and removing all edges of the chain and disconnecting one from the other edges incident with the chain. The connected splitting number is defined similarly, but now every chain (except that of the first split) must intersect a chain used in an earlier split.