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.

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Isabel Beckenbach, Ralf Borndörfer
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