For any $n\in\mathbb{N}$ let $[n] = \{1,\ldots,n\}$ and let $S\_n$ be the set of all bijections (permutations) $\pi:[n]\to [n]$. For any set $X$ let $[X]^2 = \big\{\{x,y\}: x\neq y\in X\big\}$. We let $\pi,\psi\in S\_n$ be connected by an edge if "they are one transposition away from each other", or more formally, set $$E\_n = \big\{\{\pi,\psi\}\in [S\_n]^2:\exists a<b\in[n]:\big(\psi = (a\;\;b)\circ\pi\big) \text{ or } \big(\psi = \pi\circ(a\;\; b)\big)\big\}.$$


Given any positive integer $n\in\mathbb{N}$, what is $\chi(S\_n, E\_n)$?



Chromatic number of transposition graph of permutations
For $n\geq 2$, we have
$$\chi(S\_n, E\_n) = 2.$$
It is at most $2$, since we can color permutations by their signs. It is obviously at least $2$. 


