Upload resources

Upload your works to SEDICI to increase its visibility and improve its impact

 

Show simple item record

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


Download Files

Thumbnail
Documento completo
Download file (301.0Kb) - PDF

This item appears in the following Collection(s)

Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0) Except where otherwise noted, this item's license is described as Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0)