Flavia Bonomo (1) (2), Guillermo Duran (1) (3) (4) (5), Martin D. Safe, Annegret K. Wagler (6) (7)
(1) Consejo Nacional de Investigaciones Científicas y Técnicas [Buenos Aires]
(2) Departamento de Computación [Buenos Aires]
(3) Departamento de Matemática [Buenos Aires]
(4) Departamento de Ingenieria Industrial [Santiago]
(5) Instituto de Cálculo [Buenos Aires]
(6) Laboratoire d'Informatique, de Modélisation et d'optimisation des Systèmes
(7) Université Blaise Pascal - Clermont-Ferrand 2
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.
