Flavia Bonomo ; Guillermo Duran ; Martın D. Safe ; Annegret K. Wagler - Balancedness of subclasses of circular-arc graphs

dmtcs:2100 - Discrete Mathematics & Theoretical Computer Science, June 18, 2014, Vol. 16 no. 3 - https://doi.org/10.46298/dmtcs.2100
Balancedness of subclasses of circular-arc graphsArticle

Authors: Flavia Bonomo 1,2; Guillermo Duran 1,3,4,5; Martın 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

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.


Volume: Vol. 16 no. 3
Section: Graph Theory
Published on: June 18, 2014
Submitted on: March 13, 2013
Keywords: balanced graphs,clique-perfect graphs,circular-arc graphs,coordinated graphs,perfect graphs,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Consultation statistics

This page has been seen 444 times.
This article's PDF has been downloaded 460 times.