New i-Perfect Cycle Decompositions via Vertex Colorings of Graphs

Generalizing a result by Buratti et al.[M. Buratti, F. Rania, and F. Zuanni, Some constructions for cyclic perfect cycle systems, Discrete Math 299 (2005), 33–48], we present a construction for i-perfect k-cycle decompositions of the complete m-partite graph with parts of size k. These decompositions are sharply vertex-transitive under the additive group of Zk × R, with R a suitable ring of order m. The construction works whenever a suitable i-perfect map f:Zk → R exists. We show that for determining the set of all triples (i,k,m) for which such a map exists, it is crucial to calculate the chromatic numbers of some auxiliary graphs. We completely determine this set except for one special case where k > 1, 000 is the product of two distinct primes, i > 2 is even, and gcd(m, 25) = 5. This result allows us to obtain a plethora of new i-perfect k-cycle decompositions of the complete graph of order ν ≡ k (mod 2k) with k odd. In particular, if k is a prime, such a decomposition exists for any possible i provided that gcd(v/k , 9) ≠ 3.