Some properties of edge intersection graphs of single-bend paths on a grid
- Asinowski, Andrei University of Haifa, Israel
- Ries, Bernard Université Paris-Dauphine, France
-
2012
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.
- Faculty
- Faculté des sciences économiques et sociales et du management
- Department
- Département d'informatique
- Language
-
- English
- Classification
- Computer science and technology
- License
- License undefined
- Identifiers
-
- RERO DOC 328807
- DOI 10.1016/j.disc.2011.10.005
- Persistent URL
- https://folia.unifr.ch/unifr/documents/308579
Statistics
Document views: 30
File downloads:
- 1-s2.0-s0012365x11004547-main.pdf: 59