Optimal shift coloring of trees

This paper was motivated by the problem of scheduling the openings of pharmacies during week-ends and holiday periods (shifts). The problem can be modeled as a coloring problem on a graph, which is NP-hard in general. In this paper we focus on the special case where the underlying graph is a tree, or, more generally, it is endowed with a tree-metric, and we provide a polynomial algorithm. We also provide direct optimal solutions for special trees like stars and paths.