Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4652659 | Electronic Notes in Discrete Mathematics | 2008 | 6 Pages |
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