• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

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

Thumbnail
Date
2012
Dewey
Principes généraux des mathématiques
Sujet
Erdős–Hajnal property; Neighborhood; Chordal graphs; Paths on a grid; Intersection graphs
Journal issue
Discrete Mathematics
Volume
312
Number
2
Publication date
2012
Article pages
427-440
Publisher
Elsevier
DOI
http://dx.doi.org/10.1016/j.disc.2011.10.005
URI
https://basepub.dauphine.fr/handle/123456789/8169
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Ries, Bernard
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Asinowski, Andrei
87696 Department of Computer Science [Haifa]
Type
Article accepté pour publication ou publié
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) [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 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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.