Decomposition of bipartite graphs into special subgraphs
Let F and G be two graphs and let H be a subgraph of G. A decomposition of G  into subgraphs F1,F2,,Fm F 1 , F 2 ,  , F m is called an F-factorization of G orthogonal to H  if Fi?F F i ? F and |E(Fi?H)|=1 | E ( F i ? H ) | = 1 for each i=1,2,,m i = 1 , 2 ,  , m . Gyrfs and Schelp conjectured that the complete bipartite graph K4k,4k K 4 k , 4 k has a C4 C 4 -factorization orthogonal to H provided that H is a k -factor of K4k,4k K 4 k , 4 k . In this paper, we show that (1) the conjecture is true when H  satisfies some structural conditions; (2) for any two positive integers r?k r ? k , Kkr2,kr2 K kr 2 , kr 2 has a Kr,r K r , r -factorization orthogonal to H if H is a k -factor of Kkr2,kr2 K kr 2 , kr 2 ; (3) K2d2,2d2 K 2 d 2 , 2 d 2 has a C4 C 4 -factorization such that each edge of H  belongs to a different C4 C 4 if H  is a subgraph of K2d2,2d2 K 2 d 2 , 2 d 2 with maximum degree ?(H)?d ? ( H ) ? d .
orthogonal complete bipartite graphs factorization