Balancedness of subclasses of circular-arc graphs

Mostrar todas las versiones(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, no...

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 Clique-perfect graphs Coordinated graphs Perfect graphs Characterization Graphic methods Circular-arc graph Perfect graph Graph theory
Acceso en línea:	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	todo:paper_14627264_v16_n3_p1_Bonomo
record_format	dspace
spelling	todo:paper_14627264_v16_n3_p1_Bonomo2023-10-03T16:16:39Z Balancedness of subclasses of circular-arc graphs Bonomo, F. Durán, G. Safe, M.D. Wagler, A.K. 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. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar 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, F. Durán, G. Safe, M.D. Wagler, A.K. 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.
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 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
url	http://hdl.handle.net/20.500.12110/paper_14627264_v16_n3_p1_Bonomo
work_keys_str_mv	AT bonomof balancednessofsubclassesofcirculararcgraphs AT durang balancednessofsubclassesofcirculararcgraphs AT safemd balancednessofsubclassesofcirculararcgraphs AT waglerak balancednessofsubclassesofcirculararcgraphs
_version_	1807315415153508352

Balancedness of subclasses of circular-arc graphs

Ejemplares similares