SAFE Martin Dario
Partial characterizations of circle graphs
FLAVIA BONOMO; GUILLERMO DURÁN; LUCIANO NORBERTO GRIPPO; MARTÍN DARÍO SAFE
DISCRETE APPLIED MATHEMATICS
ELSEVIER SCIENCE BV
Lugar: Amsterdam; Año: 2011 vol. 159 p. 1699 - 1706
A circle graph is the intersection graph of a family of chords on a circle. There is no known characterization of circle graphs by forbidden induced subgraphs that do not involve the notions of local equivalence or pivoting operations. We characterize circle graphs by a list of minimal forbidden induced subgraphs when the graph belongs to one of the following classes: linear domino graphs, P4-tidy graphs, and tree-cographs. We also completely characterize by minimal forbidden induced subgraphs the class of unit Helly circle graphs, which are those circle graphs having a model whose chords have all the same length, are pairwise different, and satisfy the Helly property.