1. Forbidden subgraphs and the Kőnig property.
- Author
-
Dourado, Mitre C., Durán, Guillermo, Faria, Luerbio, Grippo, Luciano N., and Safe, Martín D.
- Subjects
GRAPH theory ,MATCHING theory ,MATHEMATICAL proofs ,SET theory ,NUMBER theory ,MATHEMATICAL analysis - Abstract
Abstract: A graph has the Kőnig property if its matching number equals its transversal number. Lovász proved a characterization of graphs having the Kőnig 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 Kőnig 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 Kőnig 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 Kőnig property, we prove a forbidden subgraph characterization for the class of edge-perfect graphs. [Copyright &y& Elsevier]
- Published
- 2011
- Full Text
- View/download PDF