congresos y reuniones científicas
A linear algorithm for the k-tuple chromatic number of partner limited graphs
BONOMO, FLAVIA; KOCH, IVO; VALENCIA-PABON, MARIO
Workshop; VII Latin-American Workshop on Cliques in Graphs; 2016
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.