INVESTIGADORES
SAFE Martin Dario
artículos
Título:
Partial characterizations of circular-arc graphs
Autor/es:
FLAVIA BONOMO; GUILLERMO DURÁN; LUCIANO NORBERTO GRIPPO; MARTÍN DARÍO SAFE
Revista:
JOURNAL OF GRAPH THEORY
Editorial:
JOHN WILEY & SONS INC
Referencias:
Lugar: Hoboken, NJ; Año: 2009 vol. 61 p. 289 - 306
ISSN:
0364-9024
Resumen:
A circular-arc graph is the intersection graph of a family of arcs on a circle. A characterization by forbidden induced subgraphs for this class of graphs is not known, and in this work we present a partial result in this direction. We characterize circular-arc graphs by a list of minimal  forbidden induced subgraphs when the graph belongs to any of the following classes: P4-free graphs, paw-free graphs, claw-free chordal graphs and diamond-free graphs.