INVESTIGADORES
BONOMO flavia
congresos y reuniones científicas
Título:
Between coloring and list-coloring: \mu-coloring
Autor/es:
BONOMO, FLAVIA; CECOWSKI, MARIANO
Lugar:
Angra dos Reis
Reunión:
Simposio; II Brazilian Symposium on Graphs, Algorithms and Combinatorics (GRACO); 2005
Resumen:
A new variation of the coloring problem, mu-coloring, is defined in this paper. Given a graph G and a function mu, a mu-coloring is a coloring where each vertex v of G must receive a color at most mu(v). It is proved that mu-coloring lies between coloring and list-coloring, in the sense of generalization of problems and computational complexity. The notion of perfection is extended for mu-coloring, leading us to a new characterization of cographs. Finally, a polynomial time algorithm to solve mu-coloring for cographs is shown.