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...
Guardado en:
| Publicado: |
2009
|
|---|---|
| Materias: | |
| 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: |
| id |
paper:paper_02545330_v169_n1_p3_Bonomo |
|---|---|
| record_format |
dspace |
| spelling |
paper:paper_02545330_v169_n1_p3_Bonomo2023-06-08T15:22:00Z Exploring the complexity boundary between coloring and list-coloring Coloring Computational complexity 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 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, μ-coloring, and (γ,μ)-coloring. © 2008 Springer Science+Business Media, LLC. 2009 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 |
| institution |
Universidad de Buenos Aires |
| institution_str |
I-28 |
| repository_str |
R-134 |
| collection |
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) |
| topic |
Coloring Computational complexity List-coloring |
| spellingShingle |
Coloring Computational complexity List-coloring Exploring the complexity boundary between coloring and list-coloring |
| topic_facet |
Coloring Computational complexity List-coloring |
| description |
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, μ-coloring, and (γ,μ)-coloring. © 2008 Springer Science+Business Media, LLC. |
| title |
Exploring the complexity boundary between coloring and list-coloring |
| title_short |
Exploring the complexity boundary between coloring and list-coloring |
| title_full |
Exploring the complexity boundary between coloring and list-coloring |
| title_fullStr |
Exploring the complexity boundary between coloring and list-coloring |
| title_full_unstemmed |
Exploring the complexity boundary between coloring and list-coloring |
| title_sort |
exploring the complexity boundary between coloring and list-coloring |
| publishDate |
2009 |
| url |
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 |
| _version_ |
1768541890690416640 |