PUBLICATIONS DE L'INSTITUT MATHÉMATIQUE (BEOGRAD) (N.S.)
Vol. 33(47), pp. 157--162 (1983)
EDGE-COLORING OF A FAMILY OF REGULAR GRAPHS
Bojan Mohar, Tomazh PisanskiDepartment of Mathematics, University of Ljubljana, 61000 Ljubljana, Yugoslavia
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:
Electronic fulltext finalized on: 3 Nov 2001. This page was last modified: 16 Nov 2001.
© 2001 Mathematical Institute of the Serbian Academy of Science and Arts