TR-2001-10

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 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 egres.elte.hu}},
INSTITUTION	=	{Egerv{\'a}ry Research Group, Budapest},
YEAR	=	{2001},
NUMBER	=	{TR-2001-10}

}