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,\dots ,c_k$. If an $m$-cycle $C$ in $G$ has $n_i$ vertices colored $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$-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.