Hamilton-Waterloo Problem: Bipartite case

Abstract

Given two non-isomorphic bipartite 2-factors $F_1$ and $F_2$ of order $4n$, the Bipartite Hamilton-Waterloo Problem (BHWP) asks for a 2-factorization of $K_{2n,2n}$ into $\alpha$ copies of $F_1$ and $\beta$ copies of $F_2$, where $\alpha +\beta =n$ and $\alpha ,\beta \ge 1$. We show that the BHWP has a solution when $F_1$ is a refinement of $F_2$, where no component of $F_1$ is a $C_4$ or $C_6$, except possibly when $\alpha =1$ and either (i) $F_2$ is a $C_4$-factor or (ii) $F_2$ has more than one $C_4$ with all other components of an order $r\equiv 0(\mathrm{mod}4)>4$ or (iii) $F_2$ has components with an order $r\equiv 2(\mathrm{mod}4)$, when $n$ is even. We also show that there does not exist a factorization of $K_{6,6}$ into a single 12-cycle and two $C_4$-factors.