Let $S_n$ be the collection of bijections $\varphi:\{1,\ldots,n\}\to \{1,\ldots,n\}$. In an earlier question, the insert-and-shift graph structure was introduced on $S_n$ and the resulting graph is called $\newcommand{\Gn}{\mathbf{G}_n}\Gn$.

It turns out that $\Gn$ is not bipartite for large enough $n$. So the question is whether $\chi(\Gn)$ is bounded as $n\to\infty$. If yes, what is $$\lim\inf_{n\to\infty}\frac{\chi(\Gn)}{n}?$$

Let $S_n$ be the collection of bijections $\varphi:\{1,\ldots,n\}\to \{1,\ldots,n\}$. In an earlier question, the insert-and-shift graph structure was introduced on $S_n$ and the resulting graph is called $\newcommand{\Gn}{\mathbf{G}_n}\Gn$.

It turns out that $\Gn$ is not bipartite except for small values of $n$. So the question is whether $\chi(\Gn)$ is bounded as $n\to\infty$. If not: what is $$\lim\inf_{n\to\infty}\frac{\chi(\Gn)}{n}?$$