Restricted t-matchings in bipartite graphs

András Frank

Published in:
Discrete Applied Mathematics. 131 (2003) 337-346.


Given a simple bipartite graph G and an integer t > 1, we derive a formula for the maximum number of edges in a subgraph H of G so that H contains no node of degree larger than t and H contains no complete bipartite graph Kt,t as a subgraph. In the special case t=2 this fomula was proved earlier by Z. Király, sharpening a result of D. Hartvigsen. For any integer t > 1, we also determine the maximum number of edges in a subgraph of G that contains no complete bipartite graph, as a subgraph, with more than t nodes. The proofs are based on a general min-max result concerning crossing bi-supermodular functions.

Bibtex entry:

AUTHOR = {Frank, Andr{\'a}s},
TITLE = {Restricted t-matchings in bipartite graphs},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2001},
NUMBER = {TR-2001-10}

Last modification: 13.3.2018. Please email your comments to Tamás Király!