On coloring problems with local constraints

BONOMO, FLAVIA; FAENZA, YURI; ORIOLO, GIANPAOLO

DISCRETE MATHEMATICS

ELSEVIER SCIENCE BV

Año: 2012 vol. 312 p. 2027 - 2039

0012-365X

We deal with some generalizations of the graph coloring problem on classes of perfect graphs. Namely we consider the $mu$-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 $(gamma,mu)$-coloring problem (lower and upper bounds for thecolor 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. Theseresults have interesting corollaries. Firstly, one can observe on clique-trees of different heights the increasing complexity of the chain $k$-coloring, $mu$-coloring, $(gamma,mu)$-coloring,list-coloring. Second, clique-trees of height $2$ are the first known example of a class of graphs where $mu$-coloring is polynomial-time solvable and precoloring extension is NP-complete,thus being at the same time the first example where $mu$-coloring is polynomially solvable and $(gamma,mu)$-coloring is NP-complete. Last, we show that the $mu$-coloring problem on unit interval graphs is NP-complete. These results answer three questions from Bonomo, Dur´an, and Marenco ([Ann. Oper. Res. 169(1) (2009), 3--16]).