Authors: Flavia Bonomo Guillermo Durán Javier Marenco
Publish Date: 2008/07/02
Volume: 169, Issue: 1, Pages: 3-
Abstract
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 listcoloring problem is NPcomplete for many subclasses of perfect graphs In this work we explore the complexity boundary between vertex coloring and listcoloring on such subclasses of perfect graphs where the former admits polynomialtime algorithms but the latter is NPcomplete Our goal is to analyze the computational complexity of coloring problems lying “between” from a computational complexity viewpoint these two problems precoloring extension μcoloring and γμcoloring
Keywords: