On the Minimum Sum Coloring of P 4-Sparse Graphs

In this paper, we study the minimum sum coloring (MSC) problem on P 4-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...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autor principal: Bonomo, Flavia
Publicado: 2012
Materias:
Graph coloring
Minimum sum coloring
P 4-sparse graphs
Acceso en línea:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_09110119_v_n_p1_Bonomo
http://hdl.handle.net/20.500.12110/paper_09110119_v_n_p1_Bonomo
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id paper:paper_09110119_v_n_p1_Bonomo
record_format dspace
spelling paper:paper_09110119_v_n_p1_Bonomo2023-06-08T15:49:57Z On the Minimum Sum Coloring of P 4-Sparse Graphs Bonomo, Flavia Graph coloring Minimum sum coloring P 4-sparse graphs In this paper, we study the minimum sum coloring (MSC) problem on P 4-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 P 4-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 P 4-sparse graphs. © 2012 Springer Japan. Fil:Bonomo, F. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2012 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_09110119_v_n_p1_Bonomo http://hdl.handle.net/20.500.12110/paper_09110119_v_n_p1_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 Graph coloring
Minimum sum coloring
P 4-sparse graphs
spellingShingle Graph coloring
Minimum sum coloring
P 4-sparse graphs
Bonomo, Flavia
On the Minimum Sum Coloring of P 4-Sparse Graphs
topic_facet Graph coloring
Minimum sum coloring
P 4-sparse graphs
description In this paper, we study the minimum sum coloring (MSC) problem on P 4-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 P 4-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 P 4-sparse graphs. © 2012 Springer Japan.
author Bonomo, Flavia
author_facet Bonomo, Flavia
author_sort Bonomo, Flavia
title On the Minimum Sum Coloring of P 4-Sparse Graphs
title_short On the Minimum Sum Coloring of P 4-Sparse Graphs
title_full On the Minimum Sum Coloring of P 4-Sparse Graphs
title_fullStr On the Minimum Sum Coloring of P 4-Sparse Graphs
title_full_unstemmed On the Minimum Sum Coloring of P 4-Sparse Graphs
title_sort on the minimum sum coloring of p 4-sparse graphs
publishDate 2012
url https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_09110119_v_n_p1_Bonomo
http://hdl.handle.net/20.500.12110/paper_09110119_v_n_p1_Bonomo
work_keys_str_mv AT bonomoflavia ontheminimumsumcoloringofp4sparsegraphs
_version_ 1768541568751370240

Ejemplares similares