1
$\begingroup$

Are even order Cayley graphs of Class 1, that is, can they be edge-colored with exactly $m$ colors, where $m$ is the degree of each vertex?

I think yes, because of the symmetry the Cayley graphs possess unlike Petersen graph or Snarks. I also know of a few results in this direction in an old paper by Richard Stong. Any new conclusive result in this direction? Thanks beforehand.

$\endgroup$
22
  • 1
    $\begingroup$ I think you mean "exactly $m$ colours". $\endgroup$ Mar 9, 2019 at 14:02
  • 2
    $\begingroup$ I think this might be open, even for $3$-valent Cayley graphs. See sciencedirect.com/science/article/pii/S0095895604000188 for example. (This is more general in a way, because it deals with vertex-transitive graphs, but more restrictive, because the group is soluble.) $\endgroup$
    – verret
    Mar 9, 2019 at 20:04
  • 1
    $\begingroup$ Other than the Petersen graph and its truncation, are there actually any known vertex-transitive graphs that are not Class 1? $\endgroup$ Mar 10, 2019 at 13:18
  • 2
    $\begingroup$ Disconnected doesn’t count because that is really just an odd order graph twice over. The second one is not transitive and in that case there are many examples. $\endgroup$ Mar 12, 2019 at 14:04
  • 1
    $\begingroup$ @vidyarthi It's hard to answer a question of the form "Can we use the fact...". Can you use it? To help you see the difficulty, suppose we have a cubic Cayley graph with generating set an involution, and an element of odd order. This induces a natural partition of the edges into a perfect matching and a bunch of odd cycles. How would you use this to 3-colour the edges? Clearly, any 3-edge-colouring will NOT respect the natural edge-colouring, which makes it non-obvious why it should be useful at all. $\endgroup$
    – verret
    Mar 25, 2019 at 2:16

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.