Artículo

On the Minimum Sum Coloring of P4-sparse graphs

Bonomo, FlaviaIcon ; Valencia Pabon, Mario
Fecha de publicación: 03/2014
Editorial: Springer Tokyo
Revista: Graphs And Combinatorics
ISSN: 0911-0119
e-ISSN: 1435-5914
Idioma: Inglés
Tipo de recurso: Artículo publicado
Clasificación temática:

Resumen

In this paper, we study the Minimum Sum Coloring (MSC) problem on P4-sparse graphs. In the MSC problem, we aim to assign natural numbers to vertices of a graph such that adjacent vertices get different numbers, and the sum of the numbers assigned to the vertices is minimum. Based in the concept of maximal sequence associated with an optimal solution of the MSC problem of any graph, we show that there is a large sub-family of P4-sparse graphs for which the MSC problem can be solved in polynomial time. Moreover, we give a parameterized algorithm and a 2-approximation algorithm for the MSC problem on general P4-sparse graphs.
Palabras clave: Graph Coloring , Minimum Sum Coloring , P4-Sparse Graphs
 
Archivos asociados
Thumbnail
 
Tamaño: 196.8Kb
Formato: PDF
.
Licencia
info:eu-repo/semantics/openAccess Excepto donde se diga explícitamente, este item se publica bajo la siguiente descripción: Creative Commons Attribution-NonCommercial-ShareAlike 2.5 Unported (CC BY-NC-SA 2.5)
Identificadores
URI: http://hdl.handle.net/11336/18782
DOI: http://dx.doi.org/10.1007/s00373-012-1269-5
URL: https://link.springer.com/article/10.1007%2Fs00373-012-1269-5
Colecciones
Articulos(IMAS)
Articulos de INSTITUTO DE INVESTIGACIONES MATEMATICAS "LUIS A. SANTALO"
Citación
Bonomo, Flavia; Valencia Pabon, Mario; On the Minimum Sum Coloring of P4-sparse graphs; Springer Tokyo; Graphs And Combinatorics; 30; 2; 3-2014; 303-314
Compartir
Altmétricas