ProV Logo
0
Clique coloring B1-EPG graphs
Bonomo, Flavia...

Free

Clique coloring B1-EPG graphs by Bonomo, Flavia ( Author )
Lemonjar Open Access
N.A
22-02-2016
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.
-
Article
pdf
36.88 KB
English
-
MYR 0.01
-
https://arxiv.org/abs/1602.06723
Share this eBook