Let F and G be two graphs and let H be a subgraph of G. A decomposition of G into subgraphs F-1. F-2.....F-m is called an F-factorization of G orthogonal to H if Fi congruent to F and vertical bar E(F-i boolean AND H)vertical bar = 1 for each i = 1.2.....m. Gyarfas and Schelp conjectured that the complete bipartite graph K-4k,K-4k has a C-4-factorization orthogonal to H provided that H is a k-factor of K-4k.4k. 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, K-kr2.kr.2 has a K-r.r-factorization orthogonal to H if H is a k-factor of K-kr2.kr2; (3) K-2d2.(2d2) has a C-4-factorization such that each edge of H belongs to a different C-4 if H is a subgraph of K-2d2.2d2 with maximum degree Delta(H)<= d. (c) 2006 Elsevier B.V. All rights reserved.
展开▼
