We investigate graphs that can be represented as vertex intersections of horizontal and vertical paths in a grid, the so called B0-VPG graphs. Recognizing this class is an NP-complete problem. Although, there exists a ...

Golumbic, Lipshteyn and Stern [12] proved that every graph can be represented as the edge intersection graph of paths on a grid (EPG graph), i.e., one can associate with each vertex of the graph a nontrivial path on a ...

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

In this paper, we study the class of PVPG graphs, this is a subclass of VPG graphs such that all the representing paths are between two parallel lines of the grid and have their endpoints on these lines. We prove that PVPG ...

Golumbic, Lipshteyn and Stern [12] proved that every graph can be represented as the edge intersection graph of paths on a grid (EPG graph), i.e., one can associate with each vertex of the graph a nontrivial path on a ...

Edge intersection graphs of paths on a grid (EPG graphs) aregraphs whose vertices can be represented as nontrivial paths on agrid such that two vertices are adjacent if and only if the corresponding paths share at least ...