Some properties of edge intersection graphs of single-bend paths on a grid

AbstractIn this paper we consider graphs G whose vertices can be represented as single-bend paths (i.e., paths with at most one turn) on a rectangular grid, such that two vertices are adjacent in G if and only if the corresponding paths share at least one edge of the grid. These graphs, called B1-EPG graphs, were first introduced in Golumbic et al. (2009) [13]. Here we show that the neighborhood of every vertex in a B1-EPG graph induces a weakly chordal graph. From this we conclude that the family F of B1-EPG graphs satisfies the Erdős–Hajnal property with ϵ(F)=13, i.e., that every B1-EPG graph on n vertices contains either a clique or a stable set of size at least n13. Finally we give a characterization of B1-EPG graphs among some subclasses of chordal graphs, namely chordal bull-free graphs, chordal claw-free graphs, chordal diamond-free graphs, and special cases of split graphs