### G-95-42

# Splitting Trees

## Pierre Hansen, Alain Hertz, and N Quinodoz

Splitting a tree is defined as removing all edges of a chain and disconnecting one from the other edges incident with that chain. Splitting a forest is simultaneously splitting each of its non trivial trees. The splitting number (*T*) of a tree *T* is the minimum number of successive forest splittings which lead to deletion of all of *T*'s edges. An *O*(*N*) algorithm is proposed to get an upper bound '(*t*), the connected splitting number, on the splitting number of (*t*) of a tree *T* and an *O* (*N* log *N*) algorithm to compute this last number, where *N* is the number of vertices of the tree. Subject to a mild condition, these numbers lead to find a "black-and-white coloring" of a tree *T*. In such a coloring a large part of *T*'s vertices are colored in black or white and no two adjacent vertices receive a different color.

Published **September 1995**
,
19 pages