Partial characterizations of circular-arc graphs

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: $P_4$-free graphs, paw-free graphs, claw-free chordal graphs and diamond-free graphs.

Publicación
Journal of Graph Theory 61(4) (2009), 289–306