Is it possible to $3$-color the elements of the symmetric group $S_n\ n\ge3$ such that all color classes have the same number of elements ($\frac{n!}{3}$); and, when elements in any color class are acted by the set of transpositions $\{(12), (13), \ldots, (1n)\}$ we get no element in the same class; or, to be precise, when we act to the right by a transposition on any element to a color class, we get neighbors in both of the other color classes; and in addition, we can get a perfect matching from any two color classes.

Precisely, it is like $3$- coloring the bipartite cayley graph formed by the generating set $\{(12), (13), \ldots, (1n)\}$ on the group $S_n$, such that all color classes have same cardinality and any two color classes have a regular nontrivial(degree $\ge$ $1$) bipartite subgraph of order $2\frac{n!}{3}$.

It is easy to see this true for $n=3$. The color classes being given by $[e, (13)(12)(13)=(23)];[(12), (13)(12)]; [(13), (12)(13)]$. However as $n$ rises, I don't see a way to get this done. Specifically, I think we have to produce $\frac{n!}{6}$ $6$-cycles in the Cayley graph mentioned. But, how can this be effectively done? Can induction work here? Any hints? Thanks beforehand.

"when elements in any color class are acted by the set of transpositions.....we get no element in the same class"is quite confusing and ambiguous. What does this mean precisely? That if say, $\pi \in S_n$ is in the 1st color class, then $\tau\pi$ [or $\pi\tau$] is in either the 2nd or 3rd color class for each such transposition $\tau$? Or that there for each $j\in \{2,3\}$ exists such a transposition $\tau_j$ so that $\tau_j\pi$ [or $\pi\tau_j$] is in the $j$-th color class? $\endgroup$13more comments