INVESTIGADORES
BONOMO flavia
congresos y reuniones científicas
Título:
A linear algorithm for the k-tuple chromatic number of partner limited graphs
Autor/es:
BONOMO, FLAVIA; KOCH, IVO; VALENCIA-PABON, MARIO
Lugar:
La Plata
Reunión:
Workshop; VII Latin-American Workshop on Cliques in Graphs; 2016
Institución organizadora:
UNLP
Resumen:
In the k-tuple coloring problem, we aim to assign sets of colors of sizek to the vertices of a graph G, so that the sets which belong to adjacentvertices of G have empty intersection, and the total number of colors usedis minimum. This minimum number of colors is called the k-tuple chromaticnumber. The problem, introduced independently by Stahl and Bollobás andThomason in the late seventies, has applications in mobile radio frequencyassignments, fleet maintenance, task assignments, and traffic phasing. Wepresent in this work a linear algorithm for computing the k-tuple chromaticnumber of partner limited graphs, a graph family that generalizes manywell-known classes of graphs with ?few? induced P4s, including cographs,P4-sparse and P4-tidy graphs.