A 52-approximation algorithm for coloring rooted subtrees of a degree 3 tree

A rooted tree R is a rooted subtree of a tree T if the tree obtained by replacing the directed edges of R by undirected edges is a subtree of T. We study the problem of assigning minimum number of colors to a given set of rooted subtrees R of a given tree T such that if any two rooted subtrees share a directed edge, then they are assigned different colors. The problem is NP hard even in the case when the degree of T is restricted to at most 3 (Erlebach and Jansen, in: Proceedings of the 30th Hawaii international conference on system sciences, p 221, 1997). We present a 52-approximation algorithm for this problem. The motivation for studying this problem stems from the problem of assigning wavelengths to multicast traffic requests in all-optical WDM tree networks.