INDEPENDENT CYCLES AND PATHS IN BIPARTITE BALANCED GRAPHS

Bipartite graphs G = (L; R; E) and H = (L0; R0; E0) are bi-placeabe if there is a bijection f: L [ R! L0 [ R0 such that f(L) = L0 and f(u)f(v) =2 E0 for every edge uv 2 E. We prove that if G and H are two bipartite balanced graphs of order jGj = jH j = 2p 4 such that the sizes of G and H satisfy k G k 2p 3 and k H k 2p 2, and the maximum degree of H is at most 2, then G and H are bi-placeable, unless G and H is one of easily recognizable couples of graphs. This result implies easily that for integers p and k1; k2; : : : ; kl such that ki 2 for i = 1; : : : ; l and k1 + + kl p 1 every bipartite balanced graph G of order 2p and size at least p2 2p + 3 contains mutually vertex disjoint cycles C2k1; : : : ; C2kl, unless G = K3;33K1;1