Let $n>1$ be an integer and let $[n] = \{1,\ldots,n\}$. Let $S\_n$ denote the set of all permutations (bijections) $\pi:[n]\to[n]$. We say that $\psi\neq\pi\in S\_n$ are *a cycle away* from each other if there is an integer $k\in[n]$ and $k$ distinct integers $n\_1,\ldots n\_k\in[n]$ such that $$\psi = \pi \circ (n\_1 \; n\_2\;\cdots\; n\_k) \text{ or } \psi = (n\_1 \; n\_2\;\cdots\; n\_k) \circ \pi.$$


Let $E = \big\{\{\pi,\psi\}: \pi \neq \psi \in S\_n\text{, and} \psi,\pi \text{ are a cycle away from each other}\big\}$. This makes $(S\_n,E)$ into a connected finite, simple, undirected graph.


What is the maximal size of a clique in $(S\_n, E)$, what is $\chi(S\_n, E)$, and are these numbers equal?



Clique and chromatic number of cycle graph of permutations
It turns out that for the $S\_5$ graph the clique number is $7$ but the chromatic number is $30.$ Details at the end.


The number of cycles is $c\_n=\sum\_{k=2}^{n}\binom{n}{k}(k-1)!$ The first few terms $(n-1)!+\frac{n(n-2)!}{2}+\frac{n(n-1)(n-3)!}3$ for cycles of length $n,n-1,n-2$ are the largest. This is actually the degree of every vertex in your graph. The problem can also be reduced to one on this many vertices, but with variable degrees. That would still be an advantage.


You need only consider multiplication on one side: If $\pi$ is a permutation and $\sigma$ is a cycle Then $\sigma'=\pi \circ \sigma \circ \pi^{-1}$ is another cycle of the same type and $\sigma' \circ \pi = \pi \circ \sigma.$ 


If $C$ is a clique so is $\{\alpha\circ\pi \mid \pi \in C\}$ where $\alpha$ is an arbitrary fixed permutation. So we could assume that the identity element $i$ is a member. This in turn means that every element is a cycle.


Here is a clique of size $13$ for $S\_5$


$$ (12345)\ (12354)\ (12534)\ (13245)\ (13254)\ (14235)\ (15243)$$
$$ (132)\ (142)\ (145)\ (253)\ (345) $$
$$i$$


The cycles creating edges are exactly the $44$ cycles of type $(abc)$ and $(abcde).$ However some are used $7$ times, some $3$ and some just once.


Note that we could ask the same questions for alternating groups. This particular example lives entirely in $A\_5.$ Perhaps there is a generalization.


I find an example of size $6$ in $S\_4.$ One is $$i\ (12)\ (13)\ (14)\ (234)\ (243)$$


Since we can restrict to the $c\_n$ vertices from cycles, just look at the induced graph on these. Perhaps first look for maximal cliques among the $n$-cycles, then the $n-1$-cycles then the $n-2$-cycles. These three graphs are regular and have a high symmetry. Then see how they might be combined.


**LATER** The graph for $S\_3$ is $K\_6$ so the clique number and chromatic number are the same $6.$


I gave a clique of size $6$ in the $S\_4$ graph. For that graph (regular of degree $21$) to have chromatic number $6$ would require $6$ independent sets of size $4$. This occurs. The independent set of $\pi$ is $\{\pi,\pi(12)(34),\pi(13)(24),\pi(14)(23)\}.$


I leave the chromatic number of the $S\_5$ graph to others. Since this graph on $120$ vertices is regular of degree $84,$ It might be easier to look for cliques in the complement which has degree $35$ than independent sets in the graph.


It is curious that the clique sizes go $1,2,6,6,7$ for $n=1,2,3,4,5.$


**UPDATE** I let Maple look for the chromatic number of the $S\_5$ graph ($120$ vertices and $5040$ edges) but stopped it after several days. However it found a maximum independent set in the blink of an eye. $$i\ \ (12)(34)\ \ (13)(24)\ \
 (14)(23).$$ So at least $30$ colors are needed. Since these four elements constitute a subgroup, the left cosets of this group provide a $30$-coloring.


