INVESTIGADORES
BONOMO flavia
congresos y reuniones científicas
Título:
Partial characterizations of circle graphs
Autor/es:
BONOMO, FLAVIA; DURÁN, GUILLERMO; GRIPPO, LUCIANO NORBERTO; SAFE, MARTÍN DARÍO
Lugar:
Paris
Reunión:
Workshop; Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW); 2009
Institución organizadora:
École Polytechnique and CNAM
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 induced subgraphs that do not involve the well-known notion of local equivalence. 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, {chair,triangle}-free graphs, P_4-sparse graphs and tree-cographs. We also characterize unit Helly circle graphs.
