Exploring the complexity boundary between coloring and list-coloring
BONOMO, FLAVIA; DURÁN, GUILLERMO; MARENCO, JAVIER
ANNALS OF OPERATIONS RESEARCH
Año: 2009 vol. 169 p. 3 - 16
Many classes of graphs where the vertex coloring problem is polynomially solvable are known, the most prominent being the class of perfect graphs. However, the list-coloring problem is NP-complete for many subclasses of perfect graphs. In this work we explore the complexity boundary between vertex coloring and list-coloring on such subclasses of perfect graphs where the former admits polynomial-time algorithms but the latter is NP-complete. Our goal is to analyze the computational complexity of coloring problems lying "between" (from a computational complexity viewpoint) these two problems: precoloring extension, mu-coloring, and (gamma,mu)-coloring.