1. Forbidden subgraphs and the König-Egerváry property.
- Author
-
Bonomo, Flavia, Dourado, Mitre C., Durán, Guillermo, Faria, Luerbio, Grippo, Luciano N., and Safe, Martín D.
- Subjects
- *
SUBGRAPHS , *GRAPH theory , *PATHS & cycles in graph theory , *MATHEMATICAL models , *MATHEMATICAL analysis - Abstract
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. [ABSTRACT FROM AUTHOR]
- Published
- 2013
- Full Text
- View/download PDF