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,\dots ,c_k$ If an $m$-cycle $C$ in $G$ has $n_i$ vertices coloured $c_i$, $i=1,2,\dots ,k$, and $|n_i–n_j|\le 1$ for any $i,j\in \{1,2,\dots ,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.