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

https://hal.inria.fr/hal-01188914
Contributor : Coordination Episciences Iam <>
Submitted on : Monday, August 31, 2015 - 5:03:55 PM
Last modification on : Wednesday, April 21, 2021 - 8:52:05 AM
Long-term archiving on: : Tuesday, December 1, 2015 - 10:45:00 AM

File

dmtcs-16-3-1.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01188914, version 1

Citation

Flavia Bonomo, Guillermo Duran, Martın D. Safe, Annegret K. Wagler. Balancedness of subclasses of circular-arc graphs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2014, Vol. 16 no. 3 (in progress) (3), pp.1--22. ⟨hal-01188914⟩

Share

Metrics

Record views

299

Files downloads

918