Artículo

Clique coloring B1-EPG graphs

Bonomo, FlaviaIcon ; Mazzoleni, María PíaIcon ; Stein, Maya
Fecha de publicación: 05/2017
Editorial: Elsevier Science
Revista: Discrete Mathematics
ISSN: 0012-365X
Idioma: Inglés
Tipo de recurso: Artículo publicado
Clasificación temática:

Resumen

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.
Palabras clave: CLIQUE COLORING , EDGE INTERSECTION GRAPHS , PATHS ON GRIDS , POLYNOMIAL TIME ALGORITHM
 
Archivos asociados
Thumbnail
 
Tamaño: 361.6Kb
Formato: PDF
.
Licencia
info:eu-repo/semantics/openAccess Excepto donde se diga explícitamente, este item se publica bajo la siguiente descripción: Creative Commons Attribution-NonCommercial-ShareAlike 2.5 Unported (CC BY-NC-SA 2.5)
Identificadores
URI: http://hdl.handle.net/11336/56526
DOI: https://dx.doi.org/10.1016/j.disc.2017.01.019
URL: https://www.sciencedirect.com/science/article/pii/S0012365X17300298
Colecciones
Articulos(CCT - LA PLATA)
Articulos de CTRO.CIENTIFICO TECNOL.CONICET - LA PLATA
Articulos(ICC)
Articulos de INSTITUTO DE INVESTIGACION EN CIENCIAS DE LA COMPUTACION
Articulos(OCA CIUDAD UNIVERSITARIA)
Articulos de OFICINA DE COORDINACION ADMINISTRATIVA CIUDAD UNIVERSITARIA
Citación
Bonomo, Flavia; Mazzoleni, María Pía; Stein, Maya; Clique coloring B1-EPG graphs; Elsevier Science; Discrete Mathematics; 340; 5; 5-2017; 1008-1011
Compartir
Altmétricas