3
$\begingroup$

Let $G$ be the Cayley graph on the alternating group $A_n\,n\ge4$ with generating set $$S=\begin{cases}\{(1,2,3),(1,3,2),\\(1,2,\ldots,n),(1,n,n-1,\ldots,2)\}, &n\ \text{odd}\\ \{(1,2,3),(1,3,2),\\(2,3,\ldots,n),(2,n,n-1,\ldots,3)\}, &\text{otherwise}. \end{cases}$$ Then, will $G$ be class I, that is, have chromatic index $4$?

Though it is widely believed (though unproven) that Cayley graphs of even order are class I, but this particular graph is haunting me. For one, $A_5$ is class I, but, when I go for $A_6$, in spite of using slightly fast algorithms like mixed integer linear programming, the program (SageMath) gets stuck for hours. In addition, I tried to remove three maximum (perfect) matchings sequentially from the graph $G$ for $n=6$ to obtain a non-perfect matching with few other edges remaining, thereby possibly implying the chromatic index may be higher, which is highly unlikely. So any hints on this regard. Some fast algorithms to verify that at least $n=6$ case is class I would give some relief. In addition, I also removed the lone Hamiltonian cycle in the case $n=6$ to get a disconnected graph that required $3$ edge colors, which was not the case for $n=5$. Thanks beforehand.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

This graph is 4-colourable.

Here is some SageMath code that constructs the graph, forms its line graph and then presents a 4-colouring of the graph that you can check.

I found the colouring using the gCol package.

A6 = AlternatingGroup(6)
G = A6.cayley_graph(generators=[A6((1,2,3)), A6((2,3,4,5,6))])
G = G.to_undirected()
LG = G.line_graph()
LG2 = LG.copy()
LG2.relabel()
cols=[3,0,2,1,1,0,2,3,3,1,0,2,0,2,3,1,3,2,0,1,1,0,3,2,2,0,1,3,1,2,0,3,1,3,0,2,2,0,3,1,3,2,1,0,1,3,2,2,0,3,1,1,3,0,2,2,0,3,1,0,3,2,2,3,0,2,0,1,3,3,1,2,0,0,3,1,2,3,1,2,0,3,1,0,2,1,3,2,1,3,0,2,1,2,3,0,2,3,1,0,2,0,1,3,0,1,2,3,1,3,2,0,3,0,2,1,3,0,1,2,0,3,1,2,3,1,0,0,2,1,3,3,1,2,0,1,0,2,2,1,0,3,2,1,2,3,0,2,0,1,0,2,3,3,2,0,1,0,3,2,1,0,1,3,2,2,3,1,0,1,1,3,2,0,0,1,3,3,2,0,1,1,0,2,3,0,3,1,2,3,1,0,2,3,1,0,2,1,2,1,3,2,0,1,2,1,3,0,1,2,3,0,2,0,3,1,2,3,0,2,0,3,0,2,1,1,0,3,2,1,3,2,3,1,0,3,1,0,2,1,3,0,2,0,2,3,1,3,0,2,1,1,3,0,0,3,1,1,0,2,3,2,0,1,2,0,2,1,0,1,2,3,0,2,1,3,2,1,2,3,3,2,0,0,2,3,1,0,2,1,3,0,2,3,1,0,2,1,3,2,1,3,3,0,2,2,0,3,1,0,2,3,1,2,3,1,1,0,3,0,0,3,1,2,1,1,3,1,3,0,1,3,0,3,1,2,3,1,1,3,0,2,0,3,2,0,2,3,3,0,1,0,3,1,2,3,1,2,0,3,2,1,3,0,0,2,3,1,3,1,0,0,1,3,0,1,2,2,0,3,2,1,3,3,2,3,1,0,1,3,3,1,2,0,2,1,3,2,0,3,2,0,1,0,1,2,3,1,2,1,2,3,1,3,0,0,3,2,2,3,0,1,2,3,0,1,0,1,0,1,2,0,1,0,2,1,0,2,0,1,0,2,1,2,3,0,1,0,2,1,3,1,2,0,1,2,3,2,3,2,1,3,0,2,0,3,2,1,1,0,3,2,3,1,0,3,3,0,1,0,1,0,1,2,2,3,0,0,1,2,1,3,2,1,3,0,1,0,3,2,0,3,0,1,3,0,2,1,3,2,3,1,0,3,0,2,1,2,0,2,0,3,3,0,1,3,1,2,1,0,2,1,3,2,1,1,2,0,2,3,3,0,3,2,0,2,1,3,2,3,2,3,1,3,3,2,1,2,2,1,2,0,3,2,0,2,0,1,2,3,1,2,3,0,3,0,3,1,2,3,3,1,3,2,1,0,3,2,1,0,3,0,0,3,2,1,1,0,1,0,0,2,3,1,2,3,2,2,3,1,2,3,0,2,1,3,2,0,3,1,3,0,1,2,3,3,2,0,3,2,0,3,0,0,3,1,3,2,2,0,2,1,3,3,0,1,2,0,1,3,1,1,0,1,1,0,1,3,0,0,1,1,0,1,2,2,2,0,1,0,1,2,0,0,1,0,2,1,1,2,0,3,1,3,2,3,2,2,3,1,2,0,3,3,0,3,3,2,0,2,0,0,3,1,0,1,2,0,0,2,1,0,0,2,0,3,2,2,1,3]
for col in range(4):
    print(LG2.subgraph([x for x in range(len(cols)) if cols[x] == col]).edges())
Improve this answer
$\endgroup$
3
  • $\begingroup$ I got the output as four empty lists, which I think are the four null graphs corresponding to independent sets $\endgroup$
    – vidyarthi
    Apr 26 at 11:06
  • $\begingroup$ How do we access the gCol package in SageMath? $\endgroup$
    – vidyarthi
    Apr 26 at 11:26
  • 1
    $\begingroup$ @vidyarthi I relabel the graph so the vertices are named 0, 1, …, 719 (otherwise their names are given as triples of elements of $A_6$). The array cols gives the colour of each vertex, so that cols[i] is the colour of vertex i. The last statements form subgraphs consisting of all vertices of colour 0, then 1, then 2, then 3 and confirm that none have any edges. gCol is not part of Sage, download from rhydlewis.eu/#resources $\endgroup$
    – Gordon Royle
    Apr 26 at 11:29

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.

Not the answer you're looking for? Browse other questions tagged or ask your own question.