Skip to Main content Skip to Navigation
Journal articles

Balancedness of subclasses of circular-arc graphs

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.
Document type :
Journal articles
Complete list of metadata

Cited literature [31 references]  Display  Hide  Download
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Monday, August 31, 2015 - 5:03:55 PM
Last modification on : Sunday, June 26, 2022 - 9:36:10 AM
Long-term archiving on: : Tuesday, December 1, 2015 - 10:45:00 AM


Publisher files allowed on an open archive



Flavia Bonomo, Guillermo Duran, Martin D. Safe, Annegret K. Wagler. Balancedness of subclasses of circular-arc graphs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2014, Vol. 16 no. 3 (3), pp.1--22. ⟨10.46298/dmtcs.2100⟩. ⟨hal-01188914⟩



Record views


Files downloads