Clique coloring B1-EPG graphs

Mostrar todas las versiones(2)

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 gr...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Bonomo, Flavia, Mazzoleni, María Pía, Stein, Maya
Formato: Articulo Comunicacion
Lenguaje:Inglés
Publicado: 2017
Materias:
Matemática
Clique coloring
Edge intersection graphs
Paths on grids
Polynomial time algorithm
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/103756
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-103756
record_format dspace
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Inglés
topic Matemática
Clique coloring
Edge intersection graphs
Paths on grids
Polynomial time algorithm
spellingShingle Matemática
Clique coloring
Edge intersection graphs
Paths on grids
Polynomial time algorithm
Bonomo, Flavia
Mazzoleni, María Pía
Stein, Maya
Clique coloring B1-EPG graphs
topic_facet Matemática
Clique coloring
Edge intersection graphs
Paths on grids
Polynomial time algorithm
description 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.
format Articulo
Comunicacion
author Bonomo, Flavia
Mazzoleni, María Pía
Stein, Maya
author_facet Bonomo, Flavia
Mazzoleni, María Pía
Stein, Maya
author_sort Bonomo, Flavia
title Clique coloring B1-EPG graphs
title_short Clique coloring B1-EPG graphs
title_full Clique coloring B1-EPG graphs
title_fullStr Clique coloring B1-EPG graphs
title_full_unstemmed Clique coloring B1-EPG graphs
title_sort clique coloring b1-epg graphs
publishDate 2017
url http://sedici.unlp.edu.ar/handle/10915/103756
work_keys_str_mv AT bonomoflavia cliquecoloringb1epggraphs
AT mazzolenimariapia cliquecoloringb1epggraphs
AT steinmaya cliquecoloringb1epggraphs
bdutipo_str Repositorios
_version_ 1764820441134792705

Ejemplares similares