Subgraphs with orthogonal factorizations and algorithms

Let G=(V,E)G=(V,E) be a graph and let gg and ff be two integer-valued functions defined on VV such that n≤g(x)≤f(x)n≤g(x)≤f(x) for every x∈Vx∈V. Let H1,H2,…,HnH1,H2,…,Hn be vertex-disjoint subgraphs of GG with |E(Hi)|=k|E(Hi)|=k (1≤i≤n1≤i≤n). In this paper, we prove that every (mg+k,mf−k)(mg+k,mf−k)-graph GG contains a subgraph RR such that RR has a (g,f)(g,f)-factorization orthogonal to HiHi (1≤i≤n1≤i≤n), where mm and kk are positive integers with 1≤k