Triangulations of 3-way regular tripartite graphs of degree 4, with applications to orthogonal latin squares Original Research Article

If G is a regular tripartite graph of degree d(G) with tripartition (A,B,C) of V(G) such that the bipartite subgraphs induced by each of A ∪ B, B ∪ C, C ∪ A are all regular of degree 12d(G), then we call G 3-way regular. We give necessary and sufficient conditions for a 3-way regular tripartite graph of degree 4 to have a decomposition into edge-disjoint triangles. These yield necessary and sufficient conditions for the completion of a partial latin square of order n in which each row and column is missing exactly two symbols, and in which each symbol occurs exactly n − 2 times. We also give necessary and sufficient conditions for a 3-way regular tripartite graph of degree 4 to have a decomposition into two edge-disjoint parallel classes, each parallel class consisting of disjoint triangles. This in turn yields necessary and sufficient conditions for the completion of a pair of (n − 2) × n partial orthogonal latin squares. Generalizations of some of the various conditions are shown to be necessary in some more general contexts.