On minimal forbidden subgraph characterizations of balanced graphs

Mostrar todas las versiones(4)

A graph is balanced if its clique-matrix contains no edge-vertex incidence matrix of an odd chordless cycle as a submatrix. While a forbidden induced subgraph characterization of balanced graphs is known, there is no such characterization by minimal forbidden induced subgraphs. In this work, we prov...

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 Bipartite graphs Hereditary clique-Helly graphs Line graphs Perfect graphs Line graph Perfect graph Directed graphs Graphic methods Characterization
Acceso en línea:	http://hdl.handle.net/20.500.12110/paper_0166218X_v161_n13-14_p1925_Bonomo
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	todo:paper_0166218X_v161_n13-14_p1925_Bonomo
record_format	dspace
spelling	todo:paper_0166218X_v161_n13-14_p1925_Bonomo2023-10-03T15:03:41Z On minimal forbidden subgraph characterizations of balanced graphs Bonomo, F. Durán, G. Safe, M.D. Wagler, A.K. Balanced graphs Bipartite graphs Hereditary clique-Helly graphs Line graphs Perfect graphs Balanced graphs Bipartite graphs Hereditary clique-Helly graphs Line graph Perfect graph Directed graphs Graphic methods Characterization A graph is balanced if its clique-matrix contains no edge-vertex incidence matrix of an odd chordless cycle as a submatrix. While a forbidden induced subgraph characterization of balanced graphs is known, there is no such characterization by minimal forbidden induced subgraphs. In this work, we provide minimal forbidden induced subgraph characterizations of balanced graphs restricted to graphs that belong to one of the following graph classes: complements of bipartite graphs, line graphs of multigraphs, and complements of line graphs of multigraphs. These characterizations lead to linear-time recognition algorithms for balanced graphs within the same three graph classes. © 2013 Elsevier B.V. All rights reserved. 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_0166218X_v161_n13-14_p1925_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 Bipartite graphs Hereditary clique-Helly graphs Line graphs Perfect graphs Balanced graphs Bipartite graphs Hereditary clique-Helly graphs Line graph Perfect graph Directed graphs Graphic methods Characterization
spellingShingle	Balanced graphs Bipartite graphs Hereditary clique-Helly graphs Line graphs Perfect graphs Balanced graphs Bipartite graphs Hereditary clique-Helly graphs Line graph Perfect graph Directed graphs Graphic methods Characterization Bonomo, F. Durán, G. Safe, M.D. Wagler, A.K. On minimal forbidden subgraph characterizations of balanced graphs
topic_facet	Balanced graphs Bipartite graphs Hereditary clique-Helly graphs Line graphs Perfect graphs Balanced graphs Bipartite graphs Hereditary clique-Helly graphs Line graph Perfect graph Directed graphs Graphic methods Characterization
description	A graph is balanced if its clique-matrix contains no edge-vertex incidence matrix of an odd chordless cycle as a submatrix. While a forbidden induced subgraph characterization of balanced graphs is known, there is no such characterization by minimal forbidden induced subgraphs. In this work, we provide minimal forbidden induced subgraph characterizations of balanced graphs restricted to graphs that belong to one of the following graph classes: complements of bipartite graphs, line graphs of multigraphs, and complements of line graphs of multigraphs. These characterizations lead to linear-time recognition algorithms for balanced graphs within the same three graph classes. © 2013 Elsevier B.V. All rights reserved.
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	On minimal forbidden subgraph characterizations of balanced graphs
title_short	On minimal forbidden subgraph characterizations of balanced graphs
title_full	On minimal forbidden subgraph characterizations of balanced graphs
title_fullStr	On minimal forbidden subgraph characterizations of balanced graphs
title_full_unstemmed	On minimal forbidden subgraph characterizations of balanced graphs
title_sort	on minimal forbidden subgraph characterizations of balanced graphs
url	http://hdl.handle.net/20.500.12110/paper_0166218X_v161_n13-14_p1925_Bonomo
work_keys_str_mv	AT bonomof onminimalforbiddensubgraphcharacterizationsofbalancedgraphs AT durang onminimalforbiddensubgraphcharacterizationsofbalancedgraphs AT safemd onminimalforbiddensubgraphcharacterizationsofbalancedgraphs AT waglerak onminimalforbiddensubgraphcharacterizationsofbalancedgraphs
_version_	1807314474967760896

On minimal forbidden subgraph characterizations of balanced graphs

Ejemplares similares