Mostrar el registro sencillo del ítem
dc.contributor.author
Argiroffo, Gabriela Rut
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.contributor.author
Nasini, Graciela Leonor
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.contributor.author
Torres, Pablo Daniel
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.date.available
2017-12-12T14:04:31Z
dc.date.issued
2014-08
dc.identifier.citation
Argiroffo, Gabriela Rut; Nasini, Graciela Leonor; Torres, Pablo Daniel; The packing coloring problem for lobsters and partner limited graphs; Elsevier Science; Discrete Applied Mathematics; 164; 8-2014; 373-382
dc.identifier.issn
0166-218X
dc.identifier.uri
http://hdl.handle.net/11336/30243
dc.description.abstract
A packing k-coloring of a graph G is a k-coloring such that the distance between two vertices having color i is at least i + 1. To compute the packing chromatic number is NP-hard, even restricted to trees, and it is known to be polynomial time solvable only for a few graph classes, including cographs and split graphs. In this work, we provide upper bounds for the packing chromatic number of lobsters and we prove that it can be computed in polynomial time for an infinite subclass of them, including caterpillars. In addition, we provide superclasses of split graphs where the packing chromatic number can be computed in polynomial time. Moreover, we prove that the packing chromatic number can be computed in polynomial time for the class of partner limited graphs, a superclass of cographs, including also P4-sparse and P4-tidy graphs
dc.format
application/pdf
dc.language.iso
eng
dc.publisher
Elsevier Science
![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
Packing Chromatic Number
dc.subject
Partner Limited Graph
dc.subject
Lobster
dc.subject
Caterpillar
dc.subject.classification
Matemática Pura
![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.title
The packing coloring problem for lobsters and partner limited 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
2017-12-11T14:56:16Z
dc.journal.volume
164
dc.journal.pagination
373-382
dc.journal.pais
Países Bajos
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.journal.ciudad
Amsterdam
dc.description.fil
Fil: Argiroffo, Gabriela Rut. Universidad Nacional de Rosario; Argentina
dc.description.fil
Fil: Nasini, Graciela Leonor. Universidad Nacional de Rosario; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina
dc.description.fil
Fil: Torres, Pablo Daniel. Universidad Nacional de Rosario; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina
dc.journal.title
Discrete Applied Mathematics
![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/doi/http://dx.doi.org/10.1016/j.dam.2012.08.008
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/url/http://www.sciencedirect.com/science/article/pii/S0166218X12003083
Archivos asociados