Mostrar el registro sencillo del ítem

dc.contributor.author
Bonomo, Flavia  
dc.contributor.author
Mazzoleni, María Pía  
dc.contributor.author
Stein, Maya  
dc.date.available
2018-08-22T14:22:30Z  
dc.date.issued
2017-05  
dc.identifier.citation
Bonomo, Flavia; Mazzoleni, María Pía; Stein, Maya; Clique coloring B1-EPG graphs; Elsevier Science; Discrete Mathematics; 340; 5; 5-2017; 1008-1011  
dc.identifier.issn
0012-365X  
dc.identifier.uri
http://hdl.handle.net/11336/56526  
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.  
dc.format
application/pdf  
dc.language.iso
eng  
dc.publisher
Elsevier Science  
dc.rights
info:eu-repo/semantics/openAccess  
dc.rights.uri
https://creativecommons.org/licenses/by-nc-sa/2.5/ar/  
dc.subject
CLIQUE COLORING  
dc.subject
EDGE INTERSECTION GRAPHS  
dc.subject
PATHS ON GRIDS  
dc.subject
POLYNOMIAL TIME ALGORITHM  
dc.subject.classification
Ciencias de la Computación  
dc.subject.classification
Ciencias de la Computación e Información  
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS  
dc.subject.classification
Matemática Pura  
dc.subject.classification
Matemáticas  
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS  
dc.title
Clique coloring B1-EPG 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
2018-08-21T19:10:20Z  
dc.journal.volume
340  
dc.journal.number
5  
dc.journal.pagination
1008-1011  
dc.journal.pais
Países Bajos  
dc.journal.ciudad
Amsterdam  
dc.description.fil
Fil: Bonomo, Flavia. Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigación en Ciencias de la Computación; Argentina. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina  
dc.description.fil
Fil: Mazzoleni, María Pía. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Universidad Nacional de La Plata. Facultad de Ciencias Exactas. Departamento de Matemáticas; Argentina  
dc.description.fil
Fil: Stein, Maya. Universidad de Chile; Chile  
dc.journal.title
Discrete Mathematics  
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/doi/https://dx.doi.org/10.1016/j.disc.2017.01.019  
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/url/https://www.sciencedirect.com/science/article/pii/S0012365X17300298  

Archivos asociados
Thumbnail
 
Tamaño: 361.6Kb
Formato: PDF
.