Splitting trees

DOI10.1016/S0012-365X(96)00187-2MaRDI QIDQ1356762zbMATH OpenOpenAlexFDO

Authors Pierre Hansen, Nicolas Quinodoz, Alain Hertz

Publication date 8 October 1997

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(96)00187-2

zbMATH Keywords

black-and-white coloringchaincoloringpolynomial algorithmsplitting treestrees

Mathematics Subject Classification ID

Trees (05C05) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Review text

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.

Recommendations

• The Black-and-White Coloring Problem on Trees
• An improved algorithm for the black-and-white coloring problem on trees
• On the complexity of the black-and-white coloring problem on some classes of perfect graphs
• On tree partitions
• The black-and-white coloring problem on distance-hereditary graphs and strongly chordal graphs

Cited in

(15)

• Algorithms for vertex-partitioning problems on graphs with fixed clique-width.
• Tabu search for the BWC problem
• Anticoloring of the rook's graph
• On the complexity of the black-and-white coloring problem on some classes of perfect graphs
• The black-and-white coloring problem on distance-hereditary graphs and strongly chordal graphs
• An improved algorithm for the black-and-white coloring problem on trees
• The Black-and-White Coloring Problem on Trees
• Cutting down very simple trees
• A Reduction of the Anticoloring Problem to Connected Graphs
• scientific article; zbMATH DE number 2065939 (Why is no real title available?)
• Lazy tree splitting
• A greedy probabilistic heuristic for graph black-and-white anticoloring
• Destruction of very simple trees
• Anticoloring of a family of grid graphs
• Anticoloring and separation of graphs

This page was built for publication: Splitting trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1356762)