SAFE Martin Dario
Partial characterizations of circular-arc graphs
FLAVIA BONOMO; GUILLERMO DURÁN; LUCIANO NORBERTO GRIPPO; MARTÍN DARÍO SAFE
JOURNAL OF GRAPH THEORY
JOHN WILEY & SONS INC
Lugar: Hoboken, NJ; Año: 2009 vol. 61 p. 289 - 306
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.