B1-EPG graphs are 4-clique colorable.

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

Comodoro Rivadavia

Congreso; VI MACI 2017 - Congreso de Matemática Aplicada, Computacional e Industrial; 2017

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 thiswork we prove that B1-EPG graphs (edge intersection graphs of paths on a grid, where each path has at most onebend) are 4-clique colorable. Moreover, given a B1-EPG representation of a graph, we provide a linear time algorithmthat constructs a 4-clique coloring of it.