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

  • $\begingroup$ Oh right, thanks @bof, I corrected it $\endgroup$ – Dominic van der Zypen Jun 5 '15 at 10:00
  • 4
    $\begingroup$ @TomCeleriter no, according to the formula only monotonous cycles are considered, e.g. not (1324). $\endgroup$ – Wolfgang Jun 5 '15 at 10:40
  • $\begingroup$ Have you tried small computer examples? $\endgroup$ – 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.$

| cite | improve this answer | |

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.