# Chromatic number of graph defined on the set of permutations

For $n\in\mathbb{N}$ let $S_n$ denote the set of permutations on the set $\{1,\ldots,n\}$. Set $$E_n = \big\{\{\pi_1, \pi_2\}: \pi_1,\pi_2\in S_n \land \exists k_1 < k_2 <\ldots <k_r\leq n: \pi_2=(k_1 \cdots k_r)\circ \pi_1\big\}.$$ (In other words, $\pi_2$ can be generated from $\pi_1$ with a monotonic (or monotonic like) cyclic permutation.)

Let $G_n=(S_n, E_n)$. Given $n\in\mathbb{N}$, what is $\chi(G_n)$?

• Oh right, thanks @bof, I corrected it – Dominic van der Zypen Jun 5 '15 at 10:00
• @TomCeleriter no, according to the formula only monotonous cycles are considered, e.g. not (1324). – Wolfgang Jun 5 '15 at 10:40
• Have you tried small computer examples? – Per Alexandersson Jun 5 '15 at 14:54

In case it helps here is a Sage function that should generate these graphs (if I got the definition right)

def g(n):
gens = []
A = SymmetricGroup(n)
for el in A:
c = el.cycles()
if len(c) == 1 and sorted(c[0]) == list(c[0]):
gens += [el]
return Graph(A.cayley_graph(generators=gens, simple=True))


The chromatic number of $G_2,G_3,G_4$ and $G_5$ respectively seems to be $2,6,6,30.$