Partial Characterizations of Circular-Arc Graphs

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

Puerto Varas, Chile

Simposio; The IV Latin-American Algorithms, Graphs, and Optimization Symposium; 2007

Departamento de Ingeniería Industrial y Departamento de Ingeniería Matemática, Facultad de Ciencias Físicas y Matemáticas, Universidad de Chile

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.