Subgraphs with Orthogonal 0, k_i_1~n-Factorizations in Graphs

摘要

Let m, n, r and k_i (1 ≤ i ≤ m) be positive integers with n ≤ m and k_1 ≥ k_2 ≥ ... ≥ k_m ≥ 2r - 1. Let G be a graph, and let H_1, H_2, ... , H_r be vertex-disjoint n-subgraphs of G. It is verified in this article that every [0, k_1 + k_2 + ... + k_m - n + 1]-graph G includes a subgraph R such that R has a [0,k_i]_1~n-factorization orthogonal to every H_i, 1≤i≤r.