Randomly $r$-Orthogonal $(0,f)$-Factorizations of Bipartite $(0,mf–(m–1)r)$-Graphs

Abstract

Let $G=(X,Y,E(G))$ be a bipartite graph with vertex set $V(G)=X!Y$ and edge set $E(G)$, and let $g,f$ be two nonnegative integer-valued functions defined on $V(G)$ such that $g(x)\le f(x)$ for each $x\in V(G)$. A $(g,f)$-factor of $G$ is a spanning subgraph $F$ of $G$ such that $g(x)\le d_F(x)\le f(x)$ for each $x\in V(F)$; a $(g,f)$-factorization of $G$ is a partition of $E(G)$ into edge-disjoint $(g,f)$-factors. Let $\mathcal{F}=\{F_1,F_2,\dots ,F_m\}$ be a factorization of $G$ and $H$ be a subgraph of $G$ with $m$ edges. If $F_i$, $1\le i\le m$, has exactly $r$ edges in common with $H$, we say that $F_i$ is $r$-orthogonal to $H$. In this paper, it is proved that every bipartite $(0,mf-(m-1)r)$-graph has $(0,f)$-factorizations randomly $r$-orthogonal to any given subgraph with $m$ edges if $2r\le f(x)$ for any $x\in V(G)$.