Forbidden subgraphs and the K?nig-Egerv¨¢ry property
详细信息 查看全文
- 作者：Flavia Bonomo ; Mitre C. Dourado ; Guillermo Dur¨¢n ; Luerbio Faria ; Luciano N. Grippo ; Mart¨ªn D. Safe
- 关键词：Edge-perfect graphs ; Forbidden subgraphs ; Kö ; nig&ndash ; Egervá ; ry property ; Kö ; nig&ndash ; Egervá ; ry graphs ; Maximum matching
- 刊名：Discrete Applied Mathematics
- 出版年：2013
- 出版时间：November, 2013
- 年：2013
- 卷：161
- 期：16-17
- 页码：2380-2388
- 全文大小：424 K
文摘
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.