Given a tree T with n vertices, we show, by using a dynamic programming approach, that the problem of finding a 3–coloring of T respecting local (i.e., associated with p prespecified subsets of vertices) color bounds can be solved in O(n{6p-1} log n) time. We also show that our algorithm can be adapted to the case of k–colorings for fixed k.
