New i‐Perfect Cycle Decompositions via Vertex Colorings of Graphs. Issue 11 (22nd January 2016) - Buratti, Marco; Costa, Simone; Wang, Xiaomiao
Abstract: 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 Z k × R, with R a suitable ring of order m . The construction works whenever a suitable i‐perfect map f : Z k ⟶ 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 v ≡ k (mod 2 k ) 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 .