Subir material

Suba sus trabajos a SEDICI, para mejorar notoriamente su visibilidad e impacto

 

Mostrar el registro sencillo del ítem

dc.date.accessioned 2020-09-03T15:48:33Z
dc.date.available 2020-09-03T15:48:33Z
dc.date.issued 2017
dc.identifier.uri http://sedici.unlp.edu.ar/handle/10915/103756
dc.description.abstract We consider the problem of clique coloring, that is, coloring the vertices of a given graph such that no (maximal) clique of size at least two is monocolored. It is known that interval graphs are 2-clique colorable. In this paper we prove that B1-EPG graphs (edge intersection graphs of paths on a grid, where each path has at most one bend) are 4-clique colorable. Moreover, given a B1-EPG representation of a graph, we provide a linear time algorithm that constructs a 4-clique coloring of it. en
dc.format.extent 1008-1011 es
dc.language en es
dc.subject Clique coloring es
dc.subject Edge intersection graphs es
dc.subject Paths on grids es
dc.subject Polynomial time algorithm es
dc.title Clique coloring B1-EPG graphs en
dc.type Articulo es
sedici.identifier.other https://doi.org/10.1016/j.disc.2017.01.019 es
sedici.identifier.issn 0012-365X es
sedici.creator.person Bonomo, Flavia es
sedici.creator.person Mazzoleni, María Pía es
sedici.creator.person Stein, Maya es
sedici.subject.materias Matemática es
sedici.description.fulltext true es
mods.originInfo.place Facultad de Ciencias Exactas es
sedici.subtype Comunicacion es
sedici.rights.license Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0)
sedici.rights.uri http://creativecommons.org/licenses/by-nc-sa/4.0/
sedici.description.peerReview peer-review es
sedici.relation.journalTitle Discrete Mathematics es
sedici.relation.journalVolumeAndIssue vol. 340, no. 5 es


Descargar archivos

Thumbnail
Documento completo
Descargar archivo (301.0Kb) - PDF

Este ítem aparece en la(s) siguiente(s) colección(ones)

Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0) Excepto donde se diga explícitamente, este item se publica bajo la siguiente licencia Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0)