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
    Jun 5, 2015 at 10:40
  • $\begingroup$ Have you tried small computer examples? $\endgroup$ 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, privacy policy and cookie policy

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