Consider the alternating group graph, here defined as a Cayley graph on the alternating group $A\_n$ using the generating set $\{(1,2,3),(1,2,4),\dotsc,(1,2,n),(1,n,2),\dotsc,(1,4,2),(1,3,2)\}$. Note that when $n=3$, the graph reduces to a triangle.


Observing that the clique size is just $3$ (this can be seen by observing the structure around the identity), I propose that the graph is properly $3$-colorable for all $n$. But, can this be proved? I suppose using left cosets of $A\_3$ with respect to $A\_n$ would help us here. In fact, it helped in getting $3$-coloring for $A\_4$. Whereas, I am struck even for $A\_5$. The SageMath software gives me the expected result up to $A\_6$. Any hints?



3-coloring the alternating group graph
So I believe that $\chi(A\_7) > 3$, but this relies on some computations that require verification.


But I will start by giving some SageMath code that computes the graph, finds an independent set of size $840$, and then shows that this independent set is not a colour class in any 3-colouring.


The code is a bit clunky and roundabout because I did not originally do the computations in this order, or using SageMath, but I want to give something that anyone can at least verify.


First construct the graph, using `a7` as the group and `cset` as the connection set, and its automorphism group.



```
a7 = groups.permutation.Alternating(7)
cset = [a7([(1,2,3)]), a7([(1,2,4)]), a7([(1,2,5)]), a7([(1,2,6)]),a7([(1,2,7)])]
cset = cset + [x^-1 for x in cset]
el = list(a7)
g = Graph([range(len(el)), lambda i, j: el[i]^-1*el[j] in cset])
aut = g.automorphism_group()

```

Now (up to conjugacy) there is a unique subgroup of order $3360$ in the automorphism group with two orbits, one of length $840$ and the other of length $2 \times 840$.


I claim that the orbit of length $840$ is an independent set in the graph, and I also claim that the graph induced by the second orbit is not bipartite, thereby showing that this independent set is not a colour class in a 3-colouring.


Unfortunately, I do not know how to get SageMath to quickly find subgroups of a particular order, and the group `aut` is sufficiently large to cause my laptop to grind to a halt if I ask it to find *all* conjugacy classes of subgroups.


But let's attack it in a roundabout way. The group `aut` has order $604800$ and so it has a Sylow 7-subgroup $S$ of order $7$. The group $S$ has $360$ orbits of size $7$ and (I claim) a suitable collection of $120$ of these orbits is an independent set of size $840$.



```
s7 = aut.sylow_subgroup(7)
orbs = [Set(orb) for orb in s7.orbits()]
orbitgraph = Graph([range(len(orbs)), lambda i, j: i != j and g.subgraph(orbs[i].union(orbs[j])).num_edges() == 0])
clmax = orbitgraph.clique_maximum()
isetorbs = [orbs[i] for i in clmax]
iset = Set()
for orb in isetorbs:
    iset = iset.union(orb)
iset = sorted(iset)

```

This code calculates the orbits, then forms the “compatibility graph” on the orbits, where two orbits are connected by an edge if the two orbits can co-exist in an independent set. Then SageMath computes the maximum clique of this graph, and finally unpacks everything to get the independent set of size $840$.


Then just check that this is actually an independent set, and that its complement is not bipartite.



```
g.subgraph(iset).num_edges() == 0
g.subgraph([v for v in g.vertices() if v not in iset]).is_bipartite()

```

In fact, the complement of the 840-set has odd girth 9.


Finally, I believe that up to isomorphism there are no other independent sets of size 840 in $A\_7$, and therefore there is no $3$-colouring. But I want to do some more double-checking before then.


