Splitting trees Original Research Article

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 σ(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. Résumé La fente dʹun arbre est lʹaction qui consiste àôter toutes les arêtes dʹune de ses chaînes et à déconnecter entre elles toutes les arêtes incidentes à cette chaîne. La fente dʹune forêt est la fente simultanée de chacun de ses arbres. La sapinicitéσ(T) dʹun arbre T est le nombre minimum de fentes successives de forêts nécessaires pour ôter toutes les arêtes de T. Nous proposons un algorithme en O(N) pour obtenir une borne supérieure σ′(T) sur σ(T), et un algorithme en O(N log N) pour calculer σ(T), oùN est le nombre de sommets de T. Sous certaines conditions peu restrictives, les nombres σ(T) et σ′(T) permettent de déterminer une “coloration en noir et blanc” dʹun arbre T. Dans de telles colorations, la plupart des sommets de T sont colorés en noir ou en blanc et aucun sommet noir nʹest adjacent à un sommet blanc.