Journal article

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

Published in:
  • Discrete Mathematics. - 2012, vol. 312, no. 2, p. 427-440
English In 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 ) = 1/3 , i.e., that every B1-EPG graph on n vertices contains either a clique or a stable set of size at least n^1/3 . Finally we give a characterization of B1-EPG graphs among some subclasses of chordal graphs, namely chordal bull-free graphs, chordal clawfree graphs, chordal diamond-free graphs, and special cases of split graphs.
Faculté des sciences économiques et sociales
Département d'informatique
  • English
Computer science
License undefined
Persistent URL

Document views: 9 File downloads:
  • 1-s2.0-s0012365x11004547-main.pdf: 1