Here is a lowerbound. Note that every vertex in $G_k$ has degree $\binom{k}{2}$ since there are $\binom{k}{2}$ pairs of edges to perform a twiddle on.  Thus, the chromatic number of $G_k$ is at most $\binom{k}{2}+1$.  Therefore, in every proper colouring of $G_k$ there must be a colour class of size at least $\frac{(2k-1)!!}{\binom{k}{2}+1}$.  Be definition, this colour class is an independent set of $G_k$.