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
Autor principal: Bonomo, Flavia
Publicado: 2017
Materias:
Clique coloring
Edge intersection graphs
Paths on grids
Polynomial time algorithm
Acceso en línea:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0012365X_v340_n5_p1008_Bonomo
http://hdl.handle.net/20.500.12110/paper_0012365X_v340_n5_p1008_Bonomo
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id paper:paper_0012365X_v340_n5_p1008_Bonomo
record_format dspace
spelling paper:paper_0012365X_v340_n5_p1008_Bonomo2023-06-08T14:35:24Z Clique coloring B1-EPG graphs Bonomo, Flavia Clique coloring Edge intersection graphs Paths on grids Polynomial time algorithm 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. © 2017 Elsevier B.V. Fil:Bonomo, F. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2017 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0012365X_v340_n5_p1008_Bonomo http://hdl.handle.net/20.500.12110/paper_0012365X_v340_n5_p1008_Bonomo
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic Clique coloring
Edge intersection graphs
Paths on grids
Polynomial time algorithm
spellingShingle Clique coloring
Edge intersection graphs
Paths on grids
Polynomial time algorithm
Bonomo, Flavia
Clique coloring B1-EPG graphs
topic_facet 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. © 2017 Elsevier B.V.
author Bonomo, Flavia
author_facet Bonomo, Flavia
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 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0012365X_v340_n5_p1008_Bonomo
http://hdl.handle.net/20.500.12110/paper_0012365X_v340_n5_p1008_Bonomo
work_keys_str_mv AT bonomoflavia cliquecoloringb1epggraphs
_version_ 1768544984729911296

Ejemplares similares