Given a tree T with n vertices, we show, by using a dynamicprogramming approach, that the problem of finding a 3-coloring ofT respecting local (i.e., associated with p prespecified subsetsof vertices) color bounds can be solved in O(n6p-1 logn)time. We also show that our algorithm can be adapted to the case ofk-colorings for fixed k.