Edge-coloring of a Family of Regular Graphs

Bojan Mohar ; Tomaž Pisanski

Publications de l'Institut Mathématique, _N_S_33 (1983) no. 47, p. 157

Résumé

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.

Détail

Classification : 05C15
Keywords: regular graph, edge-coloring, factorization