Clique coloring B1-EPG graphs
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...
Guardado en:
Autores principales: | , , |
---|---|
Formato: | Articulo Comunicacion |
Lenguaje: | Inglés |
Publicado: |
2017
|
Materias: | |
Acceso en línea: | http://sedici.unlp.edu.ar/handle/10915/103756 |
Aporte de: |
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 |