Balancedness of some subclasses of circular-arc graphs

A graph is balanced if its clique-vertex incidence matrix is balanced, i.e., it does not contain a square submatrix of odd order with exactly two ones per row and per column. Interval graphs, obtained as intersection graphs of intervals of a line, are well-known examples of balanced graphs. A circul...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Bonomo, F., Durán, G., Safe, M.D., Wagler, A.K.
Formato: JOUR
Materias:
Balanced graphs
Circular-arc graphs
Forbidden subgraphs
Perfect graphs
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_15710653_v36_nC_p1121_Bonomo
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id todo:paper_15710653_v36_nC_p1121_Bonomo
record_format dspace
spelling todo:paper_15710653_v36_nC_p1121_Bonomo2023-10-03T16:27:04Z Balancedness of some subclasses of circular-arc graphs Bonomo, F. Durán, G. Safe, M.D. Wagler, A.K. Balanced graphs Circular-arc graphs Forbidden subgraphs Perfect graphs A graph is balanced if its clique-vertex incidence matrix is balanced, i.e., it does not contain a square submatrix of odd order with exactly two ones per row and per column. Interval graphs, obtained as intersection graphs of intervals of a line, are well-known examples of balanced graphs. A circular-arc graph is the intersection graph of a family of arcs on a circle. Circular-arc graphs generalize interval graphs, but are not balanced in general. In this work we characterize balanced graphs by minimal forbidden induced subgraphs restricted to graphs that belong to some classes of circular-arc graphs. © 2010 Elsevier B.V. Fil:Bonomo, F. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Durán, G. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Safe, M.D. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_15710653_v36_nC_p1121_Bonomo
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic Balanced graphs
Circular-arc graphs
Forbidden subgraphs
Perfect graphs
spellingShingle Balanced graphs
Circular-arc graphs
Forbidden subgraphs
Perfect graphs
Bonomo, F.
Durán, G.
Safe, M.D.
Wagler, A.K.
Balancedness of some subclasses of circular-arc graphs
topic_facet Balanced graphs
Circular-arc graphs
Forbidden subgraphs
Perfect graphs
description A graph is balanced if its clique-vertex incidence matrix is balanced, i.e., it does not contain a square submatrix of odd order with exactly two ones per row and per column. Interval graphs, obtained as intersection graphs of intervals of a line, are well-known examples of balanced graphs. A circular-arc graph is the intersection graph of a family of arcs on a circle. Circular-arc graphs generalize interval graphs, but are not balanced in general. In this work we characterize balanced graphs by minimal forbidden induced subgraphs restricted to graphs that belong to some classes of circular-arc graphs. © 2010 Elsevier B.V.
format JOUR
author Bonomo, F.
Durán, G.
Safe, M.D.
Wagler, A.K.
author_facet Bonomo, F.
Durán, G.
Safe, M.D.
Wagler, A.K.
author_sort Bonomo, F.
title Balancedness of some subclasses of circular-arc graphs
title_short Balancedness of some subclasses of circular-arc graphs
title_full Balancedness of some subclasses of circular-arc graphs
title_fullStr Balancedness of some subclasses of circular-arc graphs
title_full_unstemmed Balancedness of some subclasses of circular-arc graphs
title_sort balancedness of some subclasses of circular-arc graphs
url http://hdl.handle.net/20.500.12110/paper_15710653_v36_nC_p1121_Bonomo
work_keys_str_mv AT bonomof balancednessofsomesubclassesofcirculararcgraphs
AT durang balancednessofsomesubclassesofcirculararcgraphs
AT safemd balancednessofsomesubclassesofcirculararcgraphs
AT waglerak balancednessofsomesubclassesofcirculararcgraphs
_version_ 1807321118538727424

Ejemplares similares