IMAS 23417
INSTITUTO DE INVESTIGACIONES MATEMATICAS "LUIS A. SANTALO"
Unidad Ejecutora - UE
artículos
Título:
Partial characterizations of circle graphs
Autor/es:
BONOMO, FLAVIA; DURAN, GUILLERMO ALFREDO; GRIPPO, LUCIANO; SAFE, MARTIN
Revista:
DISCRETE APPLIED MATHEMATICS
Editorial:
ELSEVIER SCIENCE BV
Referencias:
Lugar: Amsterdam; Año: 2011 vol. 159 p. 1699 - 1706
ISSN:
0166-218X
Resumen:
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 inducedsubgraphs that do not involve the notions of local equivalence or pivotingoperations. We characterize circle graphs by a list of minimal forbiddeninduced subgraphs when the graph belongs to one of the following classes:linear domino graphs, P4-tidy graphs, and tree-cographs. We also completelycharacterize by minimal forbidden induced subgraphs the class of unit Hellycircle graphs, which are those circle graphs having a model whose chords haveall the same length, are pairwise di®erent, and satisfy the Helly property.
