0
$\begingroup$

From the first theorem in this paper, it is clear that a cayley graph on abelian group for all generating sets of even order is class $1$, that is can be edge colored in exactly $\Delta$ colors. But, this procedure and proof is not clear for me in the case of circulant graphs.

In the proof of the theorem $2.3$ of the above paper, the author proves the theorem for abelian groups by first proving the theorem for any graph defined on any generating set on the groups $H\rtimes G$. But, how can a graph defined on a cyclic group be written in this form? Specifically, say we have a cyclic group of order $2p$, where $p$ is $\it{odd}$. Then, though the group is isomorphic to $\mathbb{Z}_p\times\mathbb{Z}_2$, i cannot see how a graph defined on the whole group $\mathbb{Z}_{2p}$ is isomorphic to a cartesian product of graphs of the form $\Gamma(S:\mathbb{Z}_p)\times\mathbb{Z}_2$, as expected from the paper. Am I missing something? Thanks beforehand.

$\endgroup$
10
  • 2
    $\begingroup$ The 14-cycle can be coloured with two colours, but there is no reason why it must be coloured with only two colours. Using more colours on the 14-cycle may leave you more flexibility in colouring the two 7-cycles in such a way that fewer colours are required overall. $\endgroup$ Commented Aug 28, 2020 at 13:07
  • $\begingroup$ @GordonRoyle thanks! so does this imply for a general algorithm we use all the colors on all the cycles (according to their lengths)? $\endgroup$
    – vidyarthi
    Commented Aug 28, 2020 at 13:10
  • $\begingroup$ Have you tried looking at the proof of the statement you claim, to see if it gives an algorithm? $\endgroup$
    – verret
    Commented Aug 28, 2020 at 22:33
  • $\begingroup$ @verret yes. it is the stong's paper. i quite dont get the algorithm, if any, described there. And surely, this is non-trivial, for an algorithm for any circulant graph seems not easy. And your downvote seems unjustified! $\endgroup$
    – vidyarthi
    Commented Aug 28, 2020 at 22:57
  • 1
    $\begingroup$ @verret no, the paper shows that it is possible to 1-factorize the graph. But, the procedure is not clear. The paper is here $\endgroup$
    – vidyarthi
    Commented Aug 29, 2020 at 8:18

0

You must log in to answer this question.