Partial characterizations of circular-arc graphs

BONOMO, FLAVIA; DURÁN, GUILLERMO; GRIPPO, LUCIANO NORBERTO; SAFE, MARTÍN DARÍO

Puerto Varas

Simposio; Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS); 2007

Universidad de Chile

A circular-arc graph is the intersection graph of a family of arcs on a circle. A characterization by forbidden subgraphs for this class of graphs is not known. In this work we present a partial result in this direction, that is, we characterize circular-arc graphs by a list of minimal forbidden induced subgraphs when the graph belongs to the following classes: diamond-free graphs, $P_4$-free graphs, paw-free graphs, and claw-free chordal graphs.