Mostrar el registro sencillo del ítem
dc.contributor.author
Bonomo, Flavia
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.contributor.author
Durán, Guillermo Enrique
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.contributor.author
Koch, Ivo Valerio
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.contributor.author
Valencia Pabon, Mario
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.date.available
2020-04-22T15:02:07Z
dc.date.issued
2018-01
dc.identifier.citation
Bonomo, Flavia; Durán, Guillermo Enrique; Koch, Ivo Valerio; Valencia Pabon, Mario; On the (k,i)-coloring of cacti and complete graphs; Charles Babbage Res Ctr; Ars Combinatoria; 137; 1-2018; 317-333
dc.identifier.issn
0381-7032
dc.identifier.uri
http://hdl.handle.net/11336/103273
dc.description.abstract
In the (k,i)-coloring problem, we aim to assign sets of colors of size k to the vertices of a graph G, so that the sets which belong to adjacent vertices of G intersect in no more than i elements and the total number of colors used is minimum. This minimum number of colors is called the (k,i)-chromatic number. We present in this work a very simple linear time algorithm to compute an optimum (k,i)- coloring of cycles and we generalize the result in order to derive a polynomial time algorithm for this problem on cacti. We also perform a slight modification to the algorithm in order to obtain a simpler algorithm for the close coloring problem addressed in [R.C. Brigham and R.D. Dutton, Generalized k-tuple colorings of cycles and other graphs, J. Combin. Theory B 32:90–94, 1982]. Finally, we present a relation between the (k,i)-coloring problem on complete graphs and weighted binary codes.
dc.format
application/pdf
dc.language.iso
eng
dc.publisher
Charles Babbage Res Ctr
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.rights
info:eu-repo/semantics/openAccess
dc.rights.uri
https://creativecommons.org/licenses/by-nc-sa/2.5/ar/
dc.subject
Generalized k-tuple coloring
dc.subject
(k,i)-coloring
dc.subject
cactus
dc.subject
complete graphs
dc.subject.classification
Matemática Aplicada
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.subject.classification
Matemáticas
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.subject.classification
Ciencias de la Computación
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.subject.classification
Ciencias de la Computación e Información
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.title
On the (k,i)-coloring of cacti and complete graphs
dc.type
info:eu-repo/semantics/article
dc.type
info:ar-repo/semantics/artículo
dc.type
info:eu-repo/semantics/publishedVersion
dc.date.updated
2019-12-16T19:15:37Z
dc.journal.volume
137
dc.journal.pagination
317-333
dc.journal.pais
Canadá
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.journal.ciudad
WINNIPEG
dc.description.fil
Fil: Bonomo, Flavia. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina
dc.description.fil
Fil: Durán, Guillermo Enrique. Universidad de Chile; Chile. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Cálculo; Argentina. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Matemática; Argentina
dc.description.fil
Fil: Koch, Ivo Valerio. Universidad Nacional de General Sarmiento; Argentina
dc.description.fil
Fil: Valencia Pabon, Mario. Universite de Paris 13-Nord. Laboratoire d'informatique de L'Université Paris-Nord; Francia
dc.journal.title
Ars Combinatoria
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/url/http://www.combinatorialmath.ca/ArsCombinatoria/Vol137.html
Archivos asociados