Hall’s and Kőnig’s theorem in graphs and hypergraphs
- We investigate the relation between Hall’s theorem and Kőnig’s theorem in graphs and hypergraphs. In particular, we characterize the graphs satisfying a deficiency version of Hall’s theorem, thereby showing that this class strictly contains all Kőnig–Egerváry graphs. Furthermore, we give a generalization of Hall’s theorem to normal hypergraphs.
| Author: | Isabel BeckenbachORCiD, Ralf BorndörferORCiD |
|---|---|
| Document Type: | Article |
| Parent Title (English): | Discrete Mathematics |
| Volume: | 341 |
| Issue: | 10 |
| First Page: | 2753 |
| Last Page: | 2761 |
| Year of first publication: | 2018 |
| Published in: | Discrete Mathematics |
| Preprint: | urn:nbn:de:0297-zib-56175 |
| DOI: | https://doi.org/10.1016/j.disc.2018.06.013 |
