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.

what is the (0) clique number, and (1) the chromatic number, of the graph on the symmetric group which has edges between those permutations whose number of cycles in the cycle-decomposition differs by exactly 1. (One can ask this for symmetric groups on any cardinal, it still makes sense,restricting to permutations with finitely-many cycles; the OP is restricted to finite symmetric groups though.) $\endgroup$ – Peter Heinig Oct 2 '17 at 14:55the set of cyclic permutations is closed under inversion, hence an eligible Cayley-set. (And Fedor Petrov's and Aaron Meyerowitz' comments about the redundant 'or' are correct: permutations are compositions of cycles, so any two can only differ by the number of cycles in them, not by any sort of 'direction' in which they so differ.) Needless to say, useful to point out: the OP is not asking whether this Cayley graph is a perfect graph, rather only whether it's in the less well-behaved class of graphs with $\omega=\chi$. $\endgroup$ – Peter Heinig Oct 2 '17 at 14:56