Between coloring and list-coloring: μ-coloring | ||
| dc.conicet.organizacion | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Matemática | |
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigaciones Matemáticas "Luis A. Santaló" | |
| dc.conicet.organizacion | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación | |
| dc.contributor.author | Bonomo, Flavia | |
| dc.contributor.author | Cecowski Palacio, Mariano | |
| dc.date.issued | 2011-05 | |
| dc.description.abstract | 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. | es |
| dc.description.fil | Fil: Bonomo, Flavia. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Matemática; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigaciones Matemáticas "Luis A. Santaló"; Argentina | |
| dc.description.fil | Fil: Cecowski Palacio, Mariano. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina | |
| dc.format | application/pdf | es |
| dc.identifier.citation | Bonomo, Flavia; Cecowski Palacio, Mariano; Between coloring and list-coloring: μ-coloring; Charles Babbage Res Ctr; Ars Combinatoria; 99; 5-2011; 383-398 | es |
| dc.identifier.issn | 0381-7032 | |
| dc.identifier.uri | http://hdl.handle.net/11336/14910 | |
| dc.journal.ciudad | Winnipeg | es |
| dc.journal.pagination | 383-398 | es |
| dc.journal.pais | Canadá | es |
| dc.journal.title | Ars Combinatoria | es |
| dc.journal.volume | 99 | es |
| dc.language.iso | eng | es |
| dc.publisher | Charles Babbage Res Ctr | es |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/url/http://www.combinatorialmath.ca/arscombinatoria/vol99.html | |
| dc.rights | info:eu-repo/semantics/openAccess | * |
| dc.rights.uri | https://creativecommons.org/licenses/by-nc-sa/2.5/ar/ | es |
| dc.subject | Cographs | es |
| dc.subject | Coloring | es |
| dc.subject | List-Coloring | es |
| dc.subject | Μ-Coloring | es |
| dc.subject | M-Perfect Graphs | es |
| dc.subject | Perfect Graphs | es |
| dc.subject.classification | Matemática Aplicada | es |
| dc.subject.classification | Matemáticas | es |
| dc.subject.classification | CIENCIAS NATURALES Y EXACTAS | es |
| dc.subject.classification | Ciencias de la Computación | es |
| dc.subject.classification | Ciencias de la Computación e Información | es |
| dc.subject.classification | CIENCIAS NATURALES Y EXACTAS | es |
| dc.title | Between coloring and list-coloring: μ-coloring | es |
| dc.type | info:eu-repo/semantics/article | |
| dc.type | info:ar-repo/semantics/artículo | |
| dc.type | info:eu-repo/semantics/publishedVersion | |
Archivos
Bloque original
Cargando...
- Nombre:
- CONICET_Digital_Nro.18297.pdf
- Tamaño:
- 175.66 KB
- Formato:
- Adobe Portable Document Format