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 different heights, providing polynomial-time algorithms for the cases that are easy. These results have interesting corollaries. First, one can observe on clique-trees of different heights the increasing complexity of the chain k -coloring, μ -coloring, ( γ , μ ) -coloring, and list-coloring. Second, clique-trees of height 2 are the first 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 first 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 Bonomo et al. [F. Bonomo, G. Durán, J. Marenco, Exploring the complexity boundary between coloring and list-coloring, Annals of Operations Research 169 (1) (2009) 3–16].