Balancedness of some subclasses of circular-arc graphs

BONOMO, FLAVIA; DURÁN, GUILLERMO; SAFE, MARTÍN DARÍO; WAGLER, ANNEGRET KATRIN

Hammamet

Simposio; International Symposium on Combinatorial Optimization (ISCO); 2010

A graph is balanced if its clique-vertex incidence matrix is balanced, i.e., it does not contain a square submatrix of odd order with exactly two ones per row and per column. Interval graphs, obtained as intersection graphs of intervals of a line, are well-known examples of balanced graphs. A circular-arc graph is the intersection graph of a family of arcs on a circle. Circular-arc graphs generalize interval graphs, but are not balanced in general. In this work we characterize balanced graphs by minimal forbidden induced subgraphs restricted to graphs that belong to some classes of circular-arc graphs.