On coloring problems with local constraints

BONOMO, FLAVIA; FAENZA, YURI; ORIOLO, GIANPAOLO

Gramado

Simposio; Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS); 2009

We show complexity results for some generalizations of the graph coloring problem on two classes of perfect graphs, namely clique trees and unit interval graphs. We deal with 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 the color on each vertex). We characterize the complexity of all those problems on clique trees of different heights, providing polytime algorithms for the cases that are easy. These results have two interesting corollaries: first, 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 [Ann. Oper. Res. 169(1) (2009), 3-16].