Name
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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.endm.2011.05.057 | Electronic Notes in Discrete Mathematics |
Keywords | Field | DocType |
edge-perfect graphs,forbidden subgraphs,Kőnig property,Kőnig-Egerváry graphs,maximum matching | Discrete mathematics,Indifference graph,Combinatorics,Forbidden graph characterization,Chordal graph,Cograph,Trivially perfect graph,Perfect graph theorem,Mathematics,Strong perfect graph theorem,Split graph | Journal |
Volume | ISSN | Citations |
37 | 1571-0653 | 1 |
PageRank | References | Authors |
0.39 | 5 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mitre Dourado | 1 | 90 | 18.43 |
| Guillermo Durán | 2 | 296 | 29.28 |
| Luerbio Faria | 3 | 133 | 20.98 |
| Luciano N. Grippo | 4 | 28 | 7.79 |
| Martín Darío Safe | 5 | 23 | 8.99 |