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 K_{t,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:
@techreport{egres-01-10,
AUTHOR | = | {Frank, Andr{\'a}s}, |
TITLE | = | {Restricted t-matchings in bipartite graphs}, |
NOTE | = | {{\tt www.cs.elte.hu/egres}}, |
INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
YEAR | = | {2001}, |
NUMBER | = | {TR-2001-10} |