Balancedness of subclasses of circular-arc graphs
Flavia Bonomo, Guillermo Durán, Martín Darío Safe, Annegret Katrin Wagler
Abstract
A graph is balanced if its clique-vertex incidence matrix contains no
square submatrix of odd order with exactly two ones per row and per
column. There is a characterization of balanced graphs by forbidden
induced subgraphs, but no characterization by mininal
forbidden induced subgraphs is known, not even for the case of
circular-arc graphs. A circular-arc graph is the intersection graph of
a family of arcs on a circle. In this work, we characterize when a
given graph G is balanced in terms of minimal forbidden
induced subgraphs, by restricting the analysis to the case where
G belongs to certain classes of circular-arc graphs,
including Helly circular-arc graphs, claw-free circular-arc graphs,
and gem-free circular-arc graphs. In the case of gem-free circular-arc
graphs, analogous characterizations are derived for two superclasses
of balanced graphs: clique-perfect graphs and
coordinated graphs.
Full Text: PDF PostScript