Clique coloring of B1-EPG graphs

BONOMO, FLAVIA; MAZZOLENI, MARÍA PÍA; STEIN, MAYA

DISCRETE MATHEMATICS

ELSEVIER SCIENCE BV

Lugar: Amsterdam; Año: 2017 vol. 340 p. 1008 - 1011

0012-365X

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 $B_1$-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 $B_1$-EPG representation of a graph, we provide a linear time algorithm that constructs a $4$-clique coloring of it.