Exploring the complexity boundary between coloring and list-coloring

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 c...

Descripción completa

Guardado en:
Detalles Bibliográficos
Publicado: 2009
Materias:
Coloring
Computational complexity
List-coloring
Acceso en línea:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_02545330_v169_n1_p3_Bonomo
http://hdl.handle.net/20.500.12110/paper_02545330_v169_n1_p3_Bonomo
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

Ejemplares similares

Ejemplares similares