TR-2001-10

Restricted t-matchings in bipartite graphs

András Frank

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



Abstract

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:

@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}
}


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