Exploring the complexity boundary between coloring and list-coloring

BONOMO, FLAVIA; DURÁN, GUILLERMO; MARENCO, JAVIER

Lambrecht

Workshop; Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW); 2006

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.