A tree version of Konig's theorem
Loading...
Date
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Description
Konig's theorem states that the covering number and the matching number of a bipartite graph are equal. We prove a generalisation of this result, in which each point in one side of the graph is replaced by a subtree of a given tree. The proof uses a recent extension of Hall's theorem to families of hypergraphs, by the first author and P. Haxell.
6 pages, no figures. Submitted to Combinatorica. Minor mistakes in the proofs in v1 were corrected
6 pages, no figures. Submitted to Combinatorica. Minor mistakes in the proofs in v1 were corrected