Artículos de revistas
Between coloring and list-coloring: μ-coloring
Fecha
2011-05Registro en:
Bonomo, Flavia; Cecowski Palacio, Mariano; Between coloring and list-coloring: μ-coloring; Charles Babbage Res Ctr; Ars Combinatoria; 99; 5-2011; 383-398
0381-7032
Autor
Bonomo, Flavia
Cecowski Palacio, Mariano
Resumen
A new variation of the coloring problem, mu-coloring, is defined in this paper. A coloring of a graph G = (V,E) is a function f: V -> N such that f(v) is different from f(w) if v is adjacent to w. Given a graph G = (V,E) and a function mu: V -> N, G is mu-colorable if it admits a coloring f with f(v)<= mu(v) for each v in V. It is proved that mu-coloring lies between coloring and list-coloring, in the sense of generalization of problems and computational complexity. Besides, the notion of perfection is extended to mu-coloring, giving rise to a new characterization of cographs. Finally, a polynomial time algorithm to solve mu-coloring for cographs is shown.
Ítems relacionados
Mostrando ítems relacionados por Título, autor o materia.
-
Pareo de Colores mediante Búsqueda de Series de Tiempo en Bases de Datos de Color
BARRÓN FERNÁNDEZ, R.; CERVANTES ALARCÓN, F. I.; FELIPE RIVERÓN, E.M.; FIGUEROA NAZUNO, JESÚS; GUTIÉRREZ TORNÉS, A. F. -
Eugenio Rivas "El Pis": La armónica de los colores o los colores de la armónica
Fernández P., Mario