INVESTIGADORES
BONOMO Flavia
artículos
Título:
Exploring the complexity boundary between coloring and list-coloring
Autor/es:
BONOMO, FLAVIA; DURÁN, GUILLERMO; MARENCO, JAVIER
Revista:
ANNALS OF OPERATIONS RESEARCH
Editorial:
Springer
Referencias:
Año: 2009 vol. 169 p. 3 - 16
ISSN:
0254-5330
Resumen:
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.