Diamond-Free Circle Graphs are Helly Circle - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Article Dans Une Revue Discrete Mathematics Année : 2010

Diamond-Free Circle Graphs are Helly Circle

Jean Daligault
  • Fonction : Auteur
  • PersonId : 857844
Michaël Rao

Résumé

The \emph{diamond} is the graph obtained from $K_4$ by deleting an edge. \emph{Circle graphs} are the intersection graphs of chords in a circle. Such a circle model has the \emph{Helly property} if every three pairwise intersecting chords intersect in a single point, and a graph is \emph{Helly circle} if it has a circle model with the Helly property. We show that the Helly circle graphs are the diamond-free circle graphs, as conjectured by Durán. This characterization gives an efficient recognition algorithm for Helly circle graphs.
Fichier principal
Vignette du fichier
HellyCircle_submitted.pdf (206.32 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

lirmm-00432897 , version 1 (17-11-2009)

Identifiants

Citer

Jean Daligault, Daniel Gonçalves, Michaël Rao. Diamond-Free Circle Graphs are Helly Circle. Discrete Mathematics, 2010, 310 (4), pp.845-849. ⟨10.1016/j.disc.2009.09.022⟩. ⟨lirmm-00432897⟩
209 Consultations
186 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More