Edge coloring of a graph on alternating groups

Question

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.

Answer 1

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())