The solution of the bipartite analogue of the Oberwolfach problem (Q1184002): Difference between revisions

The Oberwolfach problem, as proposed by \textit{G. Ringel} in 1967 (cf., e.g., \textit{R. K. Guy} [Unsolved combinatorial problems, Combinat. Math. Appl., Proc. Conf. math. Inst. Oxford 1969, 121-127 (1971; Zbl 0221.05003)]) asks whether it is possible to decompose the complete graph \(K_{2m+1}\) into \(m\) 2-regular factors, each isomorphic to a given 2- regular factor \(F\). It has been conjectured that the answer is ``yes'' unless \(F\) is isomorphic to \(C_ 4\cup C_ 5\) or to \(C_ 3\cup C_ 3\cup C_ 5\) in which cases the answer is known to be ``no''. In the present paper, the author completely solves the bipartite variant of the problem: If \(F\) is a 2-regular graph consisting of a disjoint union of cycles of lengths \(a_ 1,\dots,a_ s\) \((a_ i\geq 3)\) then the complete bipartite graph \(K_{n,n}\) can be decomposed into factors isomorphic to \(F\) if and only if \(n\) and all \(a_ i\)'s are even integers, \(\Sigma a_ i=2n\), and \(F\) is not isomorphic to \(C_ 6\cup C_ 6\). The method used is that of so-called pathlike factorizations. An application of the method to the original Oberwolfach problem yields the following theorem: If \(t,a_ 0,a_ 1,\dots,a_ k\) are integers with \(t\geq 1\), \(k\geq 0\), \(a_ i>(2t+1)(4t+1)\) and \(n=\Sigma a_ i\equiv 2t+3\pmod{4t+4}\) then the complete graph \(K_ n\) can be decomposed into factors isomorphic to \(C_{a_ 0}\cup C_{a_ 1}\cup\cdots\cup C_{a_ k}\).