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.

Improve this question
$\endgroup$
22
  • 1
    $\begingroup$ I think you mean "exactly $m$ colours". $\endgroup$
    – Chris Godsil
    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$
    – Gordon Royle
    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$
    – Gordon Royle
    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

Reset to default

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.