Subgraphs with orthogonal factorizations and algorithms Changping Wang

摘要

Let G = (V, E) be a graph and let g and f be two integer-valued functions defined on V such that n <= g(x) <= f (x) for every x is an element of V. Let H-1, H-2, ..., H-n be vertex-disjoint subgraphs of G with vertical bar E(H-i)vertical bar = k (1 <= i <= n). In this paper, we prove that every (mg + k, mf - k)-graph G contains a subgraph R such that R has a (g, f)-factorization orthogonal to H-i (1 <= i <= n), where m and k are positive integers with 1 <= k <= m. We also prove that there are polynomial-time algorithms for finding the desired subgraph R.