Some equitably 2-colourable cycle decompositions of multipartite graphs

Abstract

Let G be a graph in which each vertex has been coloured using one of k colours, say c₁, c₂, . . . , c_k. If an m-cycle C in G has x_i vertices coloured c_i, i = 1, 2, . . . , k, and |x_i - x_j| ≤ 1 for any c_i, c_j ∈ {c₁, c₂, . . . , c_k}, then C is said to be equitably k-coloured. An m-cycle decomposition C of a graph G is equitably k-colourable if the vertices of G can be coloured so that every m-cycle in C is equitably k-coloured. For m = 3 and 5 we completely settle the existence problem for equitably 2-colourable m-cycle decompositions of complete multipartite graphs with all parts the same size, while for m = 4 and 6 we settle the same problem for all complete multipartite graphs.