On coloring problems with local constraints

We deal with some generalizations of the graph coloring problem on classes of perfect graphs. Namely we consider the -coloring problem (upper bounds for the color on each vertex), the precoloring extension problem (a subset of vertices colored beforehand), and a problem generalizing both of them, the (γ,µ )-coloring problem (lower and upper bounds for the color on each vertex). We characterize the complexity of all those problems on clique trees of di erent heights, providing polytime algorithms for the cases that are easy. These results have two interesting corollaries: rst, one can observe on clique trees of di erent heights the increasing complexity of the chain k-coloring, µ -coloring, (γ,µ )-coloring, list-coloring. Second, clique trees of height 2 are the rst known example of a class of graphs where -coloring is polynomial time solvable and precoloring extension is NP-complete, thus being at the same time the rst example where -coloring is polynomially solvable and (γ,µ )-coloring is NP-complete. Last, we show that the -coloring problem on unit interval graphs is NP-complete. These results answer three questions from [Ann. Oper. Res. 169(1) (2009), 3{16].