Halving Complete $4$-Partite Graphs

Abstract

We completely determine the spectrum (i.e. set of orders) of complete $4$-partite graphs with at most one odd part which are decomposable into two isomorphic factors with a finite diameter. For complete $4$-partite graphs with all parts odd we solve the spectrum problem completely for factors with diameter $5$. As regards the remaining possible finite diameters, $2,3,4$, we present partial results, focusing on decompositions of $K_{n,n,n,m}$ and $K_{n,n,m,m}$ for odd $m$ and $n$.