Skip to main content
2 of 2
added 417 characters in body
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

Here are some upper and lower bounds.

The paper On the chromatic number of some flip graphs proves that the chromatic number of $G_k$ is at most $4k-4$. Therefore, in every proper colouring of $G_k$ there must be a colour class of size at least $\frac{(2k-1)!!}{4k-4}$. Thus, $\alpha(G_k) \geq \frac{(2k-1)!!}{4k-4}$.

On the other hand, the eigenvalues of $G_k$ are well-known and using the Hoffman Ratio Bound, we obtain $\alpha(G_k) \leq \frac{(2k-1)!!}{3}$.

Better bounds are known for small values of $k$. For example, at the end of the paper On the flip graphs on perfect matchings of the complete graphs and signed reversal graphs, they note that $\alpha(G_4)=28$ and $\alpha(G_5) \geq 208$.

Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187