| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4648723 | Discrete Mathematics | 2010 | 5 Pages |
Abstract
The diamond is the graph obtained from K4K4 by deleting an edge. Circle graphs are the intersection graphs of chords in a circle. Such a circle model has the Helly property if every three pairwise intersecting chords intersect in a single point, and a graph is 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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Jean Daligault, Daniel Gonçalves, Michaël Rao,