Edge-coloring of a Family of Regular Graphs


Bojan Mohar, Tomazh Pisanski


Let $G(m)$ denote the composition graph $G[mK_1]$. An obvious necessary condition for $G(m)$ to be 1-factorable is that $G$ is regular and $mp$ is even, where $p$ is the number of vertices of $G$. It is conjectured that this is also a sufficient condition. For regular $G$ it is proved that $G(m)$ is 1-factorable if at least one of the following conditions is satisfied: (a) $G$ is 1-factorable, (b) $G$ is of even degree and $m$ is even, (c) $m$ is divisible by 4, (d) $G$ has a 1-factor and $m$ is even, (e) $G$ is cubic and $m$ is even. The results are used to solve some other problems.