Mostrar el registro sencillo del ítem
dc.contributor.author
Severin, Daniel Esteban
dc.date.available
2022-10-21T19:35:08Z
dc.date.issued
2020-06
dc.identifier.citation
Severin, Daniel Esteban; On the additive chromatic number of several families of graphs; Elsevier Science; Information Processing Letters; 158; 6-2020; 1-5
dc.identifier.issn
0020-0190
dc.identifier.uri
http://hdl.handle.net/11336/174445
dc.description.abstract
The Additive Coloring Problem is a variation of the Coloring Problem where labels of {1,…,k} are assigned to the vertices of a graph G so that the sum of labels over the neighborhood of each vertex is a proper coloring of G. The least value k for which G admits such labeling is called additive chromatic number of G. This problem was first presented by Czerwiński, Grytczuk and Żelazny who also proposed a conjecture that for every graph G, the additive chromatic number never exceeds the classic chromatic number. Up to date, the conjecture has been proved for complete graphs, trees, non-3-colorable planar graphs with girth at least 13 and non-bipartite planar graphs with girth at least 26. In this work, we show that the conjecture holds for split graphs. We also present exact formulas for computing the additive chromatic number for some subfamilies of split graphs (complete split, headless spiders and complete sun), regular bipartite, complete multipartite, fan, windmill, circuit, wheel, cycle sun and wheel sun.
dc.format
application/pdf
dc.language.iso
eng
dc.publisher
Elsevier Science
dc.rights
info:eu-repo/semantics/restrictedAccess
dc.rights.uri
https://creativecommons.org/licenses/by-nc-sa/2.5/ar/
dc.subject
ADDITIVE CHROMATIC NUMBER
dc.subject
ADDITIVE COLORING CONJECTURE
dc.subject
GRAPH ALGORITHMS
dc.subject
LUCKY LABELING
dc.subject.classification
Matemática Aplicada
dc.subject.classification
Matemáticas
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS
dc.title
On the additive chromatic number of several families of 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
2022-09-19T15:11:22Z
dc.journal.volume
158
dc.journal.pagination
1-5
dc.journal.pais
Países Bajos
dc.journal.ciudad
Amsterdam
dc.description.fil
Fil: Severin, Daniel Esteban. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Rosario; Argentina. Universidad Nacional de Rosario. Facultad de Ciencias Exactas Ingeniería y Agrimensura. Escuela de Ciencias Exactas y Naturales. Departamento de Matemática; Argentina
dc.journal.title
Information Processing Letters
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/url/https://linkinghub.elsevier.com/retrieve/pii/S0020019020300247
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1016/j.ipl.2020.105937
Archivos asociados