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

BONOMO, FLAVIA; COSTA DOURADO, MITRE ; DURÁN, GUILLERMO; FARIA, LUERBIO; GRIPPO, LUCIANO NORBERTO; SAFE, MARTÍN DARÍO

DISCRETE APPLIED MATHEMATICS

ELSEVIER SCIENCE BV

Lugar: Amsterdam; Año: 2013 vol. 161 p. 2380 - 2388

0166-218X

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.