Diamond-Free Circle Graphs are Helly Circle
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.
Domains
Discrete Mathematics [cs.DM]Origin | Files produced by the author(s) |
---|