info:eu-repo/semantics/article
Clique coloring B1-EPG graphs
Fecha
2017-05Registro en:
Bonomo, Flavia; Mazzoleni, María Pía; Stein, Maya; Clique coloring B1-EPG graphs; Elsevier Science; Discrete Mathematics; 340; 5; 5-2017; 1008-1011
0012-365X
CONICET Digital
CONICET
Autor
Bonomo, Flavia
Mazzoleni, María Pía
Stein, Maya
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.