Packing complete multipartite graphs with 4-cycles (Q2713360)

A \(k\)-cycle packing of a graph \(G\) is a set \(C\) of edge-disjoint \(k\)-cycles in \(G\). A \(k\)-cycle packing \(C\) of \(G\) is maximum if \(|C|\geq |C'|\) for all other \(k\)-cycle packings \(C'\) of \(G\). The leave of a \(k\)-cycle packing \(C\) of \(G\) is the set of edges of \(G\) that occur in no \(k\)-cycle in \(C\). The authors completely solve the problem of finding a maximum 4-cycle packing of any complete multipartite graph, and they present the minimum leaves explicitly. This is a very interesting extension and generalization of known results by \textit{J. Schönheim} and \textit{A. Bialostocki} [Can. Math. Bull. 18, 703-708 (1975; Zbl 0322.05139)] and \textit{D. G. Hoffman} and \textit{W. D. Wallis} [Bull. Inst. Comb. Appl. 1, 89-92 (1991; Zbl 0828.05051)], where this problem has been solved for complete graphs.