Skip to Main content Skip to Navigation
Journal articles

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.
Document type :
Journal articles
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00432897
Contributor : Jean Daligault <>
Submitted on : Tuesday, November 17, 2009 - 3:44:24 PM
Last modification on : Thursday, February 7, 2019 - 2:51:35 PM
Long-term archiving on: : Thursday, June 17, 2010 - 8:42:47 PM

File

HellyCircle_submitted.pdf
Files produced by the author(s)

Identifiers

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⟩

Share

Metrics

Record views

456

Files downloads

251