Some Equitably \(2\)-colorable Cycle Decompositions of \(K_v + I\)

Abstract

Let \(G\) be a graph in which each vertex has been colored using one of \(k\) colors, say \(c_1, c_2, \ldots, c_k\). If an \(m\)-cycle \(C\) in \(G\) has \(n_i\) vertices colored \(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\)-colored. An \(m\)-cycle decomposition \(\mathcal{C}\) of a graph \(G\) is equitably \(k\)-colorable if the vertices of \(G\) can be colored so that every \(m\)-cycle in \(\mathcal{C}\) is equitably \(k\)-colored. For \(m = 4, 5\), and \(6\), we completely settle the existence problem for equitably \(2\)-colorable \(m\)-cycle decompositions of complete graphs with the edges of a \(1\)-factor added.