On coloring problems with local constraints

We show complexity results for some generalizations of the graph coloring problem on two classes of perfect graphs, namely clique trees and unit interval graphs. We deal with the μ-coloring problem (upper bounds for the color on each vertex), the precoloring extension problem (a subset of vertices c...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autor principal: Bonomo, Flavia
Publicado: 2009
Materias:
clique trees
computational complexity
graph coloring problems
unit interval graphs
Acceso en línea:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v35_nC_p215_Bonomo
http://hdl.handle.net/20.500.12110/paper_15710653_v35_nC_p215_Bonomo
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id paper:paper_15710653_v35_nC_p215_Bonomo
record_format dspace
spelling paper:paper_15710653_v35_nC_p215_Bonomo2023-06-08T16:24:25Z On coloring problems with local constraints Bonomo, Flavia clique trees computational complexity graph coloring problems unit interval graphs We show complexity results for some generalizations of the graph coloring problem on two classes of perfect graphs, namely clique trees and unit interval graphs. We deal with the μ-coloring problem (upper bounds for the color on each vertex), the precoloring extension problem (a subset of vertices colored beforehand), and a problem generalizing both of them, the (γ, μ)-coloring problem (lower and upper bounds for the color on each vertex). We characterize the complexity of all those problems on clique trees of different heights, providing polytime algorithms for the cases that are easy. These results have two interesting corollaries: first, one can observe on clique trees of different heights the increasing complexity of the chain k-coloring, μ-coloring, (γ, μ)-coloring, list-coloring. Second, clique trees of height 2 are the first known example of a class of graphs where μ-coloring is polynomial time solvable and precoloring extension is NP-complete, thus being at the same time the first example where μ-coloring is polynomially solvable and (γ, μ)-coloring is NP-complete. Last, we show that the μ-coloring problem on unit interval graphs is NP-complete. These results answer three questions from [Ann. Oper. Res. 169(1) (2009), 3-16]. © 2009 Elsevier B.V. All rights reserved. Fil:Bonomo, F. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2009 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v35_nC_p215_Bonomo http://hdl.handle.net/20.500.12110/paper_15710653_v35_nC_p215_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 clique trees
computational complexity
graph coloring problems
unit interval graphs
spellingShingle clique trees
computational complexity
graph coloring problems
unit interval graphs
Bonomo, Flavia
On coloring problems with local constraints
topic_facet clique trees
computational complexity
graph coloring problems
unit interval graphs
description We show complexity results for some generalizations of the graph coloring problem on two classes of perfect graphs, namely clique trees and unit interval graphs. We deal with the μ-coloring problem (upper bounds for the color on each vertex), the precoloring extension problem (a subset of vertices colored beforehand), and a problem generalizing both of them, the (γ, μ)-coloring problem (lower and upper bounds for the color on each vertex). We characterize the complexity of all those problems on clique trees of different heights, providing polytime algorithms for the cases that are easy. These results have two interesting corollaries: first, one can observe on clique trees of different heights the increasing complexity of the chain k-coloring, μ-coloring, (γ, μ)-coloring, list-coloring. Second, clique trees of height 2 are the first known example of a class of graphs where μ-coloring is polynomial time solvable and precoloring extension is NP-complete, thus being at the same time the first example where μ-coloring is polynomially solvable and (γ, μ)-coloring is NP-complete. Last, we show that the μ-coloring problem on unit interval graphs is NP-complete. These results answer three questions from [Ann. Oper. Res. 169(1) (2009), 3-16]. © 2009 Elsevier B.V. All rights reserved.
author Bonomo, Flavia
author_facet Bonomo, Flavia
author_sort Bonomo, Flavia
title On coloring problems with local constraints
title_short On coloring problems with local constraints
title_full On coloring problems with local constraints
title_fullStr On coloring problems with local constraints
title_full_unstemmed On coloring problems with local constraints
title_sort on coloring problems with local constraints
publishDate 2009
url https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v35_nC_p215_Bonomo
http://hdl.handle.net/20.500.12110/paper_15710653_v35_nC_p215_Bonomo
work_keys_str_mv AT bonomoflavia oncoloringproblemswithlocalconstraints
_version_ 1768546741585444864

Ejemplares similares