Subir material

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

 

Mostrar el registro sencillo del ítem

dc.date.accessioned 2019-08-26T17:44:25Z
dc.date.available 2019-08-26T17:44:25Z
dc.date.issued 2017
dc.identifier.uri http://sedici.unlp.edu.ar/handle/10915/79817
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 work 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 166-168 es
dc.language en es
dc.subject clique coloring, edge intersection graphs, paths on grids, polynomial time algorithm es
dc.title B1-EPG graphs are 4-clique colorable en
dc.type Objeto de conferencia es
sedici.identifier.issn 2314-3282 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 Objeto de conferencia 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.date.exposure 2017
sedici.relation.event VI Congreso de Matemática Aplicada, Computacional e Industrial (MACI) (Comodoro Rivadavia, 2 al 5 de mayo de 2017) es
sedici.description.peerReview peer-review es


Descargar archivos

Thumbnail
Documento completo
Descargar archivo (337.7Kb) - 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)