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)$?

  • 4
    $\begingroup$ @TomCeleriter no, according to the formula only monotonous cycles are considered, e.g. not (1324). $\endgroup$
    – Wolfgang
    Commented Jun 5, 2015 at 10:40
  • $\begingroup$ Have you tried small computer examples? $\endgroup$ Commented Jun 5, 2015 at 14:54

1 Answer 1


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.$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.