Bijection on the set of proper colorings of a graph Let $G(V,E)$ be a graph with $|V|=n$ and let there be $q$ colors (which is fixed). The set of proper colorings $\mathcal{X}$ of $G$ is the set of functions from $x:\{1,2,\ldots,q\}\to V$ such that $x(v)\neq x(w)$ for all $(v,w)\in E$.
Now I know that any bijection $f:\mathbb{Z}_q\to \mathbb{Z}_q$ induces a bijection $g:\mathcal{X} \to \mathcal{X}$ where $g(x)(v):=f(x(v))$ (Here $x\in \mathcal{X}$). The number of proper colorings grows exponentially with $n$. Since $q$ is fixed, for large $n$, the number of bijections $f:\mathbb{Z}_q\to \mathbb{Z}_q$ (which is $q!$) is a lot smaller than the number of bijections $g:\mathcal{X} \to \mathcal{X}$. Thus:

I am trying to find examples of bijections $g:\mathcal{X} \to \mathcal{X}$ which are not induced by $f:\mathbb{Z}_q\to \mathbb{Z}_q$ and which also mix (i.e. permute) $\mathcal{X}$ well?

 A: Take the graph composed of a path of length 2, with vertices labelled $a-b-c$.
Let $q=3$.
$x_1(a)=1, x_1(b)=2, x_1(c)=3$ and $x_2(a)=1, x_2(b)=2, x_2(c)=1$, $x_1, x_2 \in \mathcal{X}$ are two proper colorings that can't be deduced by a simple permutation of colors.
You can take here $g(x_1) = x_2, \; g(x_2) = x_1, \;g(x) = x \;\forall x \neq x_1, x_2$. This function is obviously a bijection, and can't be induced by an $f$, because we would have $x_1(a) = g(x_2)(a) = f(x_2(a)) = f(x_2(c)) = g(x_2)(c) = x_1(c)$, which is a contradiction.
This can be generalized to any graph $G$, any integer $q$, as long as there exists two $q$-colorings $x_1$, $x_2$ that can't be deduced by a permutation of colors, i.e where we have two vertices $a$ and $b$ such that $x_1(a) \neq x_1(b)$ but $x_2(a) = x_2(b)$. This is not always possible since a graph can have a unique proper coloring up to permutation of colors. For example, takes the triangle graph with $q =3$. Each vertex must have a different color, so we have $3!$ proper colorings, one for each permutation of 3 colors.
We can even have a number of proper colorings smaller than $q$. For a triangle graph, the number of proper coloring is $3! {q \choose 3} = \dfrac{q!}{(q-3)!} < q!$ when $q > 3$.
