Diamond-Free Circle Graphs are Helly Circle

Jean Daligault 1 Daniel Gonçalves 1 Michaël Rao 2
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : 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.
Type de document :
Article dans une revue
Discrete Mathematics, Elsevier, 2010, 310 (4), pp.845-849. 〈10.1016/j.disc.2009.09.022〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00432897
Contributeur : Jean Daligault <>
Soumis le : mardi 17 novembre 2009 - 15:44:24
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13
Document(s) archivé(s) le : jeudi 17 juin 2010 - 20:42:47

Fichier

HellyCircle_submitted.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Jean Daligault, Daniel Gonçalves, Michaël Rao. Diamond-Free Circle Graphs are Helly Circle. Discrete Mathematics, Elsevier, 2010, 310 (4), pp.845-849. 〈10.1016/j.disc.2009.09.022〉. 〈lirmm-00432897〉

Partager

Métriques

Consultations de la notice

307

Téléchargements de fichiers

84