Abstract:

Let G be a bipartite graph with vertex set V (G) and edge set E(G), and let g and f be two positive integer-valued functions defined on V (G) such that g(x)  f(x) for every vertex x of V (G). Then a (g, f)-factor of G is a spanning subgraph H of G such that g(x)  dH(x)  f(x) for each x 2 V (H). A (g, f)-factorization of G is a partition of E(G) into edge-disjoint (g, f)-factors. Let F = {F1, F2, · · · , Fm} and H be a factorization and a subgraph of G, respectively. If Fi, 1  i  m, has exactly one edge in common with H, then it is said that F is orthogonal to H. It is proved that every bipartite
(mg+m−1,mf −m+1)-graph G has a (g, f)-factorization orthogonal to k vertex disjoint m-subgraphs of G if k 2  g(x) for all x 2 V (G). Furthermore, it is showed that the results in this paper are best possible.

Key words: Bipartite graph, (g, f)-factor, orthogonal factorization