INVESTIGADORES
BONOMO flavia
congresos y reuniones científicas
Título:
Minimum Sum Coloring of P_4-sparse graphs
Autor/es:
BONOMO, FLAVIA; VALENCIA-PABON, MARIO
Lugar:
Gramado
Reunión:
Simposio; Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS); 2009
Resumen:
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. First, we introduce the concept of maximal sequence associated with an optimal solution of the MSC problem of any graph. Next, based in such maximal sequences, 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.