INVESTIGADORES
BONOMO flavia
artículos
Título:
On coloring problems with local constraints
Autor/es:
BONOMO, FLAVIA; FAENZA, YURI; ORIOLO, GIANPAOLO
Revista:
DISCRETE MATHEMATICS
Editorial:
ELSEVIER SCIENCE BV
Referencias:
Año: 2012 vol. 312 p. 2027 - 2039
ISSN:
0012-365X
Resumen:
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]).