Forbidden subgraphs and the Ko{double acute}nig property

A graph has the Konig property if its matching number equals its transversal number. Lovász proved a characterization of graphs having the Konig property by forbidden subgraphs, restricted to graphs with a perfect matching. Korach, Nguyen, and Peis proposed an extension of Lovász's result to a...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Durán, Guillermo A., Grippo, Luciano Norberto, Safe, Martín Darío
Publicado:	2011
Materias:	Edge-perfect graphs Forbidden subgraphs Ko{double acute}nig property Ko{double acute}nig-Egerváry graphs Maximum matching
Acceso en línea:	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v37_nC_p333_Dourado http://hdl.handle.net/20.500.12110/paper_15710653_v37_nC_p333_Dourado
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	paper:paper_15710653_v37_nC_p333_Dourado
record_format	dspace
spelling	paper:paper_15710653_v37_nC_p333_Dourado2023-06-08T16:24:27Z Forbidden subgraphs and the Ko{double acute}nig property Durán, Guillermo A. Grippo, Luciano Norberto Safe, Martín Darío Edge-perfect graphs Forbidden subgraphs Ko{double acute}nig property Ko{double acute}nig-Egerváry graphs Maximum matching A graph has the Konig property if its matching number equals its transversal number. Lovász proved a characterization of graphs having the Konig property by forbidden subgraphs, restricted to 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 Konig property in terms of forbidden configurations (certain arrangements of a subgraph and a maximum matching). In this work, we prove a characterization of graphs having the Konig property in terms of forbidden subgraphs which is a strengthened version of the characterization by Korach et al. As a consequence of our characterization of graphs with the Konig property, we prove a forbidden subgraph characterization for the class of edge-perfect graphs. © 2011 Elsevier B.V. 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. 2011 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v37_nC_p333_Dourado http://hdl.handle.net/20.500.12110/paper_15710653_v37_nC_p333_Dourado
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 Ko{double acute}nig property Ko{double acute}nig-Egerváry graphs Maximum matching
spellingShingle	Edge-perfect graphs Forbidden subgraphs Ko{double acute}nig property Ko{double acute}nig-Egerváry graphs Maximum matching Durán, Guillermo A. Grippo, Luciano Norberto Safe, Martín Darío Forbidden subgraphs and the Ko{double acute}nig property
topic_facet	Edge-perfect graphs Forbidden subgraphs Ko{double acute}nig property Ko{double acute}nig-Egerváry graphs Maximum matching
description	A graph has the Konig property if its matching number equals its transversal number. Lovász proved a characterization of graphs having the Konig property by forbidden subgraphs, restricted to 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 Konig property in terms of forbidden configurations (certain arrangements of a subgraph and a maximum matching). In this work, we prove a characterization of graphs having the Konig property in terms of forbidden subgraphs which is a strengthened version of the characterization by Korach et al. As a consequence of our characterization of graphs with the Konig property, we prove a forbidden subgraph characterization for the class of edge-perfect graphs. © 2011 Elsevier B.V.
author	Durán, Guillermo A. Grippo, Luciano Norberto Safe, Martín Darío
author_facet	Durán, Guillermo A. Grippo, Luciano Norberto Safe, Martín Darío
author_sort	Durán, Guillermo A.
title	Forbidden subgraphs and the Ko{double acute}nig property
title_short	Forbidden subgraphs and the Ko{double acute}nig property
title_full	Forbidden subgraphs and the Ko{double acute}nig property
title_fullStr	Forbidden subgraphs and the Ko{double acute}nig property
title_full_unstemmed	Forbidden subgraphs and the Ko{double acute}nig property
title_sort	forbidden subgraphs and the ko{double acute}nig property
publishDate	2011
url	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v37_nC_p333_Dourado http://hdl.handle.net/20.500.12110/paper_15710653_v37_nC_p333_Dourado
work_keys_str_mv	AT duranguillermoa forbiddensubgraphsandthekodoubleacutenigproperty AT grippolucianonorberto forbiddensubgraphsandthekodoubleacutenigproperty AT safemartindario forbiddensubgraphsandthekodoubleacutenigproperty
_version_	1768542663387119616

Forbidden subgraphs and the Ko{double acute}nig property

Ejemplares similares