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, Flavia, Durán, Guillermo A., Safe, Martín Darío
Publicado: 2010
Materias:
Balanced graphs
Circular-arc graphs
Forbidden subgraphs
Perfect graphs
Acceso en línea:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v36_nC_p1121_Bonomo
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 paper:paper_15710653_v36_nC_p1121_Bonomo
record_format dspace
spelling paper:paper_15710653_v36_nC_p1121_Bonomo2023-06-08T16:24:26Z Balancedness of some subclasses of circular-arc graphs Bonomo, Flavia Durán, Guillermo A. Safe, Martín Darío 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. 2010 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v36_nC_p1121_Bonomo 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, Flavia
Durán, Guillermo A.
Safe, Martín Darío
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.
author Bonomo, Flavia
Durán, Guillermo A.
Safe, Martín Darío
author_facet Bonomo, Flavia
Durán, Guillermo A.
Safe, Martín Darío
author_sort Bonomo, Flavia
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
publishDate 2010
url https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v36_nC_p1121_Bonomo
http://hdl.handle.net/20.500.12110/paper_15710653_v36_nC_p1121_Bonomo
work_keys_str_mv AT bonomoflavia balancednessofsomesubclassesofcirculararcgraphs
AT duranguillermoa balancednessofsomesubclassesofcirculararcgraphs
AT safemartindario balancednessofsomesubclassesofcirculararcgraphs
_version_ 1768545946823557120

Ejemplares similares