EDGE-COLORING OF A FAMILY OF REGULAR GRAPHS

Bojan Mohar, Tomazh Pisanski

Abstract: 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.

Keywords: regular graph, edge-coloring, factorization

Classification (MSC2000): 05C15

Full text of the article:

• Compressed PostScript file (77 kilobytes)
• PDF file (247 kilobytes)