Some properties of edge intersection graphs of single-bend paths on a grid
Ries, Bernard; Asinowski, Andrei (2012), Some properties of edge intersection graphs of single-bend paths on a grid, Discrete Mathematics, 312, 2, p. 427-440. 10.1016/j.disc.2011.10.005
TypeArticle accepté pour publication ou publié
Journal nameDiscrete Mathematics
MetadataShow full item record
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Department of Computer Science [Haifa]
Abstract (EN)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) . 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 View the MathML source, i.e., that every B1-EPG graph on n vertices contains either a clique or a stable set of size at least View the MathML source. 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.
Subjects / KeywordsErdős–Hajnal property; Neighborhood; Chordal graphs; Paths on a grid; Intersection graphs
Showing items related by title and author.
On the Intersection Graphs of Orthogonal Line Segments in the Plane: Characterizations of Some Subclasses of Chordal Graphs Golumbic, Martin Charles; Ries, Bernard (2013) Article accepté pour publication ou publié
Ries, Bernard; Pop, Petrica; Monnot, Jérôme; Demange, Marc (2014) Article accepté pour publication ou publié