Diamond-Free Circle Graphs are Helly Circle - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Journal Articles Discrete Mathematics Year : 2010

Diamond-Free Circle Graphs are Helly Circle

Jean Daligault
  • Function : Author
  • PersonId : 857844
Michaël Rao

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.
Fichier principal
Vignette du fichier
HellyCircle_submitted.pdf (206.32 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

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

Identifiers

Cite

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⟩
217 View
194 Download

Altmetric

Share

More