On Factors with Prescribed Degrees in Bipartite Graphs

Abstract

We establish a new criterion for a bigraph to have a subgraph with prescribed degree conditions. We show that the bigraph $G[X,Y]$ has a spanning subgraph $F$ such that $g(x)\le de{g}_F(x)\le f(x)$ for $x\in X$ and $de{g}_F(y)\le f(y)$ for $y\in Y$ if and only if ${\sum }_{b\in B}f(b)\ge {\sum }_{a\in A}\max \{0,g(a)-de{g}_{G-B}(a)\}$ for $A\subseteq X,B\subseteq Y$. Using Folkman-Fulkerson's Theorem, Cymer and Kano found a different criterion for the existence of such a subgraph (Graphs Combin. 32 (2016), 2315--2322). Our proof is self-contained and relies on alternating path technique. As an application, we prove the following extension of Hall's theorem. A bigraph $G[X,Y]$ in which each edge has multiplcity at least $m$ has a subgraph $F$ with $g(x)\le de{g}_F(x)\le f(x)\le deg(x)$ for $x\in X$, $de{g}_F(y)\le m$ for $y\in Y$ if and only if ${\sum }_{y\in N_G(S)}f(y)\ge {\sum }_{x\in S}g(x)$ for $S\subseteq X$.

3 pages