Article ID Journal Published Year Pages File Type
4652659 Electronic Notes in Discrete Mathematics 2008 6 Pages PDF
Abstract

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 the following classes: diamond-free graphs, P4-free graphs, paw-free graphs, and claw-free chordal graphs.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics