Decomposition of Complete Tripartite Graphs into Gregarious 3-Paths and 6-Cycles

Abstract

In this paper, we refer to a decomposition of a tripartite graph into paths of length $3$, or into $6$-cycles, as gregarious if each subgraph has at least one vertex in each of the three partite sets. For a tripartite graph to have a $6$-cycle decomposition it is straightforward to see that all three parts must have even size. Here we provide a gregarious decomposition of a complete tripartite graph $K(r,s,t)$ into paths of length $3$, and thus of $K(2r,2s,2t)$ into gregarious $6$-cycles, in all possible cases, when the straightforward necessary conditions on $r,s,t$ are satisfied.