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

Mostrar todas las versiones(3)

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, F., Dourado, M.C., Durán, G., Faria, L., Grippo, L.N., Safe, M.D.
Formato: Artículo publishedVersion
Lenguaje:Inglés
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: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 paperaa:paper_0166218X_v161_n16-17_p2380_Bonomo
record_format dspace
spelling paperaa:paper_0166218X_v161_n16-17_p2380_Bonomo2023-06-12T16:46:56Z Forbidden subgraphs and the König-Egerváry property Discrete Appl Math 2013;161(16-17):2380-2388 Bonomo, F. Dourado, M.C. Durán, G. Faria, L. Grippo, L.N. Safe, M.D. 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 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_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)
language Inglés
orig_language_str_mv eng
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, F.
Dourado, M.C.
Durán, G.
Faria, L.
Grippo, L.N.
Safe, M.D.
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.
format Artículo
Artículo
publishedVersion
author Bonomo, F.
Dourado, M.C.
Durán, G.
Faria, L.
Grippo, L.N.
Safe, M.D.
author_facet Bonomo, F.
Dourado, M.C.
Durán, G.
Faria, L.
Grippo, L.N.
Safe, M.D.
author_sort Bonomo, F.
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 http://hdl.handle.net/20.500.12110/paper_0166218X_v161_n16-17_p2380_Bonomo
work_keys_str_mv AT bonomof forbiddensubgraphsandthekonigegervaryproperty
AT douradomc forbiddensubgraphsandthekonigegervaryproperty
AT durang forbiddensubgraphsandthekonigegervaryproperty
AT farial forbiddensubgraphsandthekonigegervaryproperty
AT grippoln forbiddensubgraphsandthekonigegervaryproperty
AT safemd forbiddensubgraphsandthekonigegervaryproperty
_version_ 1769810179700817920

Ejemplares similares