Forbidden subgraphs and the König-Egerváry property

The matching number of a graph is the maximum size of a set of vertex-disjoint edges. The transversal number is the minimum number of vertices needed to meet every edge. A graph has the König-Egerváry property if its matching number equals its transversal number. Lovász proved a characterization of...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Bonomo, Flavia, Durán, Guillermo A., Grippo, Luciano Norberto, Safe, Martín Darío
Publicado:	2013
Materias:	Edge-perfect graphs Forbidden subgraphs König-Egerváry graphs König-Egerváry property Maximum matching Forbidden configurations Forbidden subgraph characterizations Matching numbers Maximum matchings Perfect matchings Transversal number Characterization Graphic methods Graph theory
Acceso en línea:	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v161_n16-17_p2380_Bonomo http://hdl.handle.net/20.500.12110/paper_0166218X_v161_n16-17_p2380_Bonomo
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	paper:paper_0166218X_v161_n16-17_p2380_Bonomo
record_format	dspace
spelling	paper:paper_0166218X_v161_n16-17_p2380_Bonomo2023-06-08T15:15:32Z Forbidden subgraphs and the König-Egerváry property Bonomo, Flavia Durán, Guillermo A. Grippo, Luciano Norberto Safe, Martín Darío Edge-perfect graphs Forbidden subgraphs König-Egerváry graphs König-Egerváry property Maximum matching Edge-perfect graphs Forbidden configurations Forbidden subgraph characterizations Forbidden subgraphs Matching numbers Maximum matchings Perfect matchings Transversal number Characterization Graphic methods Graph theory The matching number of a graph is the maximum size of a set of vertex-disjoint edges. The transversal number is the minimum number of vertices needed to meet every edge. A graph has the König-Egerváry property if its matching number equals its transversal number. Lovász proved a characterization of graphs having the König-Egerváry property by means of forbidden subgraphs within graphs with a perfect matching. Korach, Nguyen, and Peis proposed an extension of Lovász's result to a characterization of all graphs having the König-Egerváry property in terms of forbidden configurations (which are certain arrangements of a subgraph and a maximum matching). In this work, we prove a characterization of graphs having the König-Egerváry property by means of forbidden subgraphs which is a strengthened version of the characterization by Korach et al. Using our characterization of graphs with the König-Egerváry property, we also prove a forbidden subgraph characterization for the class of edge-perfect graphs. © 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:Grippo, L.N. 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 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v161_n16-17_p2380_Bonomo http://hdl.handle.net/20.500.12110/paper_0166218X_v161_n16-17_p2380_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	Edge-perfect graphs Forbidden subgraphs König-Egerváry graphs König-Egerváry property Maximum matching Edge-perfect graphs Forbidden configurations Forbidden subgraph characterizations Forbidden subgraphs Matching numbers Maximum matchings Perfect matchings Transversal number Characterization Graphic methods Graph theory
spellingShingle	Edge-perfect graphs Forbidden subgraphs König-Egerváry graphs König-Egerváry property Maximum matching Edge-perfect graphs Forbidden configurations Forbidden subgraph characterizations Forbidden subgraphs Matching numbers Maximum matchings Perfect matchings Transversal number Characterization Graphic methods Graph theory Bonomo, Flavia Durán, Guillermo A. Grippo, Luciano Norberto Safe, Martín Darío Forbidden subgraphs and the König-Egerváry property
topic_facet	Edge-perfect graphs Forbidden subgraphs König-Egerváry graphs König-Egerváry property Maximum matching Edge-perfect graphs Forbidden configurations Forbidden subgraph characterizations Forbidden subgraphs Matching numbers Maximum matchings Perfect matchings Transversal number Characterization Graphic methods Graph theory
description	The matching number of a graph is the maximum size of a set of vertex-disjoint edges. The transversal number is the minimum number of vertices needed to meet every edge. A graph has the König-Egerváry property if its matching number equals its transversal number. Lovász proved a characterization of graphs having the König-Egerváry property by means of forbidden subgraphs within graphs with a perfect matching. Korach, Nguyen, and Peis proposed an extension of Lovász's result to a characterization of all graphs having the König-Egerváry property in terms of forbidden configurations (which are certain arrangements of a subgraph and a maximum matching). In this work, we prove a characterization of graphs having the König-Egerváry property by means of forbidden subgraphs which is a strengthened version of the characterization by Korach et al. Using our characterization of graphs with the König-Egerváry property, we also prove a forbidden subgraph characterization for the class of edge-perfect graphs. © 2013 Elsevier B.V. All rights reserved.
author	Bonomo, Flavia Durán, Guillermo A. Grippo, Luciano Norberto Safe, Martín Darío
author_facet	Bonomo, Flavia Durán, Guillermo A. Grippo, Luciano Norberto Safe, Martín Darío
author_sort	Bonomo, Flavia
title	Forbidden subgraphs and the König-Egerváry property
title_short	Forbidden subgraphs and the König-Egerváry property
title_full	Forbidden subgraphs and the König-Egerváry property
title_fullStr	Forbidden subgraphs and the König-Egerváry property
title_full_unstemmed	Forbidden subgraphs and the König-Egerváry property
title_sort	forbidden subgraphs and the könig-egerváry property
publishDate	2013
url	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v161_n16-17_p2380_Bonomo http://hdl.handle.net/20.500.12110/paper_0166218X_v161_n16-17_p2380_Bonomo
work_keys_str_mv	AT bonomoflavia forbiddensubgraphsandthekonigegervaryproperty AT duranguillermoa forbiddensubgraphsandthekonigegervaryproperty AT grippolucianonorberto forbiddensubgraphsandthekonigegervaryproperty AT safemartindario forbiddensubgraphsandthekonigegervaryproperty
_version_	1768543224700338176

Forbidden subgraphs and the König-Egerváry property

Ejemplares similares