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

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 onsome upper and lower bounds. Thus,

The paper On the chromatic number of some flip graphs proves that the chromatic number of $G_k$ is at most $\binom{k}{2}+1$$4k-4$. Therefore 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}$$\frac{(2k-1)!!}{4k-4}$. Be definition Thus, this colour class is an independent set$\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$.

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$.

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$.

Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

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$.