A Combinatorial Proof of a König-type Theorem for Unimodular Hypergraphs

Please always quote using this URN: urn:nbn:de:0297-zib-64017
under review
  • We state purely combinatorial proofs for König- and Hall-type theorems for a wide class of combinatorial optimization problems. Our methods rely on relaxations of the matching and vertex cover problem and, moreover, on the strong coloring properties admitted by bipartite graphs and their generalizations.

Download full text files

Export metadata

Metadaten
Author:Isabel Beckenbach, Britta Peis, Oliver Schaudt, Robert Scheidweiler
Document Type:ZIB-Report
Tag:Covering; Factors; König's Theorem; Packing; Total Unimodularity
MSC-Classification:05-XX COMBINATORICS (For finite fields, see 11Txx) / 05Cxx Graph theory (For applications of graphs, see 68R10, 81Q30, 81T15, 82B20, 82C20, 90C35, 92E10, 94C15) / 05C65 Hypergraphs
05-XX COMBINATORICS (For finite fields, see 11Txx) / 05Cxx Graph theory (For applications of graphs, see 68R10, 81Q30, 81T15, 82B20, 82C20, 90C35, 92E10, 94C15) / 05C70 Factorization, matching, partitioning, covering and packing
Date of first Publication:2017/05/16
Series (Serial Number):ZIB-Report (17-27)
ISSN:1438-0064