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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2014, Vol. 16 no. 3 (in progress) (3), pp.1--22
Liste complète des métadonnées

Littérature citée [31 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01188914
Contributeur : Coordination Episciences Iam <>
Soumis le : lundi 31 août 2015 - 17:03:55
Dernière modification le : jeudi 29 novembre 2018 - 11:50:02
Document(s) archivé(s) le : mardi 1 décembre 2015 - 10:45:00

Fichier

dmtcs-16-3-1.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

227

Téléchargements de fichiers

311