Show simple item record

Clique coloring B1-EPG graphs

Authordc.contributor.authorBonomo, Flavia 
Authordc.contributor.authorMazzoleni, María Pía 
Authordc.contributor.authorStein, Maya 
Admission datedc.date.accessioned2019-05-29T13:29:55Z
Available datedc.date.available2019-05-29T13:29:55Z
Publication datedc.date.issued2017
Cita de ítemdc.identifier.citationDiscrete Mathematics 340 (2017) 1008–1011
Identifierdc.identifier.issn0012365X
Identifierdc.identifier.other10.1016/j.disc.2017.01.019
Identifierdc.identifier.urihttps://repositorio.uchile.cl/handle/2250/168878
Abstractdc.description.abstractWe 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.
Lenguagedc.language.isoen
Publisherdc.publisherElsevier
Type of licensedc.rightsAttribution-NonCommercial-NoDerivs 3.0 Chile
Link to Licensedc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/3.0/cl/
Sourcedc.sourceDiscrete Mathematics
Keywordsdc.subjectClique coloring
Keywordsdc.subjectEdge intersection graphs
Keywordsdc.subjectPaths on grids
Keywordsdc.subjectPolynomial time algorithm
Títulodc.titleClique coloring B1-EPG graphs
Document typedc.typeArtículo de revista
Catalogueruchile.catalogadorlaj
Indexationuchile.indexArtículo de publicación SCOPUS
uchile.cosechauchile.cosechaSI


Files in this item

Icon
Name:
Clique-coloring-B1-EPG-graphs.pdf
Size:
380.9Kb
Format:
PDF

This item appears in the following Collection(s)

Show simple item record

Attribution-NonCommercial-NoDerivs 3.0 Chile
Except where otherwise noted, this item's license is described as Attribution-NonCommercial-NoDerivs 3.0 Chile