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

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Bonomo, F., Mazzoleni, M.P., Stein, M.
Formato: JOUR
Materias:
Clique coloring
Edge intersection graphs
Paths on grids
Polynomial time algorithm
Acceso en línea: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 todo:paper_0012365X_v340_n5_p1008_Bonomo
record_format dspace
spelling todo:paper_0012365X_v340_n5_p1008_Bonomo2023-10-03T14:10:22Z Clique coloring B1-EPG graphs Bonomo, F. Mazzoleni, M.P. Stein, M. 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. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar 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, F.
Mazzoleni, M.P.
Stein, M.
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.
format JOUR
author Bonomo, F.
Mazzoleni, M.P.
Stein, M.
author_facet Bonomo, F.
Mazzoleni, M.P.
Stein, M.
author_sort Bonomo, F.
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
url http://hdl.handle.net/20.500.12110/paper_0012365X_v340_n5_p1008_Bonomo
work_keys_str_mv AT bonomof cliquecoloringb1epggraphs
AT mazzolenimp cliquecoloringb1epggraphs
AT steinm cliquecoloringb1epggraphs
_version_ 1807323456502497280

Ejemplares similares