Some Equitably \(2\)-Colourable Cycle Decompositions

Abstract

Let \(G\) be a graph in which each vertex has been coloured using one of \(k\) colours, say \(c_1,c_2,\ldots,c_k\) If an \(m\)-cycle \(C\) in \(G\) has \(n_i\) vertices coloured \(c_i\), \(i = 1,2,\ldots,k\), and \(|n_i – n_j| \leq 1\) for any \(i,j \in \{1,2,\ldots,k\}\), then \(C\) is 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 = 4,5\) and \(6\), we completely settle the existence problem for equitably \(2\)-colourable \(m\)-cycle decompositions of complete graphs and complete graphs with the edges of a \(1\)-factor removed.