Balancedness of subclasses of circular-arc graphs

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, no...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Bonomo, Flavia, Durán, Guillermo A., Safe, Martín Darío
Publicado:	2014
Materias:	Balanced graphs Circular-arc graphs Clique-perfect graphs Coordinated graphs Perfect graphs Characterization Graphic methods Circular-arc graph Perfect graph Graph theory
Acceso en línea:	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_14627264_v16_n3_p1_Bonomo http://hdl.handle.net/20.500.12110/paper_14627264_v16_n3_p1_Bonomo
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	paper:paper_14627264_v16_n3_p1_Bonomo
record_format	dspace
spelling	paper:paper_14627264_v16_n3_p1_Bonomo2025-07-30T18:52:01Z Balancedness of subclasses of circular-arc graphs Bonomo, Flavia Durán, Guillermo A. Safe, Martín Darío Balanced graphs Circular-arc graphs Clique-perfect graphs Coordinated graphs Perfect graphs Characterization Graphic methods Balanced graphs Circular-arc graph Clique-perfect graphs Coordinated graphs Perfect graph Graph theory 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. © 2014 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France. 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. 2014 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_14627264_v16_n3_p1_Bonomo http://hdl.handle.net/20.500.12110/paper_14627264_v16_n3_p1_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 Clique-perfect graphs Coordinated graphs Perfect graphs Characterization Graphic methods Balanced graphs Circular-arc graph Clique-perfect graphs Coordinated graphs Perfect graph Graph theory
spellingShingle	Balanced graphs Circular-arc graphs Clique-perfect graphs Coordinated graphs Perfect graphs Characterization Graphic methods Balanced graphs Circular-arc graph Clique-perfect graphs Coordinated graphs Perfect graph Graph theory Bonomo, Flavia Durán, Guillermo A. Safe, Martín Darío Balancedness of subclasses of circular-arc graphs
topic_facet	Balanced graphs Circular-arc graphs Clique-perfect graphs Coordinated graphs Perfect graphs Characterization Graphic methods Balanced graphs Circular-arc graph Clique-perfect graphs Coordinated graphs Perfect graph Graph theory
description	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. © 2014 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France.
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 subclasses of circular-arc graphs
title_short	Balancedness of subclasses of circular-arc graphs
title_full	Balancedness of subclasses of circular-arc graphs
title_fullStr	Balancedness of subclasses of circular-arc graphs
title_full_unstemmed	Balancedness of subclasses of circular-arc graphs
title_sort	balancedness of subclasses of circular-arc graphs
publishDate	2014
url	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_14627264_v16_n3_p1_Bonomo http://hdl.handle.net/20.500.12110/paper_14627264_v16_n3_p1_Bonomo
work_keys_str_mv	AT bonomoflavia balancednessofsubclassesofcirculararcgraphs AT duranguillermoa balancednessofsubclassesofcirculararcgraphs AT safemartindario balancednessofsubclassesofcirculararcgraphs
_version_	1840322474839900160

Balancedness of subclasses of circular-arc graphs

Ejemplares similares