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:	Artículo publishedVersion
Lenguaje:	Inglés
Publicado:	2013
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	paperaa:paper_0166218X_v161_n13-14_p1925_Bonomo
record_format	dspace
spelling	paperaa:paper_0166218X_v161_n13-14_p1925_Bonomo2023-06-12T16:46:56Z On minimal forbidden subgraph characterizations of balanced graphs Discrete Appl Math 2013;161(13-14):1925-1942 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. 2013 info:eu-repo/semantics/article info:ar-repo/semantics/artículo info:eu-repo/semantics/publishedVersion application/pdf eng 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)
language	Inglés
orig_language_str_mv	eng
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	Artículo Artículo publishedVersion
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
publishDate	2013
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_	1769810285476970496

On minimal forbidden subgraph characterizations of balanced graphs

Ejemplares similares