Some properties of edge intersection graphs of singlebend paths on a grid
Published in:
 Discrete Mathematics.  2012, vol. 312, no. 2, p. 427440
English
In this paper we consider graphs G whose vertices can be represented as singlebend 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 B1EPG graphs, were first introduced in Golumbic et al. (2009) [13]. Here we show that the neighborhood of every vertex in a B1EPG graph induces a weakly chordal graph. From this we conclude that the family F of B1EPG graphs satisfies the Erdős–Hajnal property with ϵ(F ) = 1/3 , i.e., that every B1EPG 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 B1EPG graphs among some subclasses of chordal graphs, namely chordal bullfree graphs, chordal clawfree graphs, chordal diamondfree graphs, and special cases of split graphs.

Faculty
 Faculté des sciences économiques et sociales et du management

Department
 Département d'informatique

Language


Classification

Computer science

License

License undefined

Identifiers


Persistent URL

https://folia.unifr.ch/unifr/documents/308579
Statistics
Document views: 18
File downloads:
 1s2.0s0012365x11004547main.pdf: 26