Skip to main content
MathOverflow

Return to Answer

edited body
Source Link
kabenyuk
kabenyuk
  • 673
  • 1
  • 4
  • 13

Here's a good example.

Let $G=S_n$, $S=\{(i,j)\mid 1\leq i<j\leq n \}$. Then $\operatorname{Cay}(G,S)$ is a bipartite graph and so its chromatic number is $2$. Let $H=\{g\in S_n\mid g(n)=n\}$. It is easy to check that $\operatorname{Cay}(G/H,S)$$\operatorname{Sch}(G/H,S)$ is a complete graph (if we forget about loops) and hence its chromatic number is $n$.

Here's a good example.

Let $G=S_n$, $S=\{(i,j)\mid 1\leq i<j\leq n \}$. Then $\operatorname{Cay}(G,S)$ is a bipartite graph and so its chromatic number is $2$. Let $H=\{g\in S_n\mid g(n)=n\}$. It is easy to check that $\operatorname{Cay}(G/H,S)$ is a complete graph (if we forget about loops) and hence its chromatic number is $n$.

Here's a good example.

Let $G=S_n$, $S=\{(i,j)\mid 1\leq i<j\leq n \}$. Then $\operatorname{Cay}(G,S)$ is a bipartite graph and so its chromatic number is $2$. Let $H=\{g\in S_n\mid g(n)=n\}$. It is easy to check that $\operatorname{Sch}(G/H,S)$ is a complete graph (if we forget about loops) and hence its chromatic number is $n$.

Source Link
kabenyuk
kabenyuk
  • 673
  • 1
  • 4
  • 13

Here's a good example.

Let $G=S_n$, $S=\{(i,j)\mid 1\leq i<j\leq n \}$. Then $\operatorname{Cay}(G,S)$ is a bipartite graph and so its chromatic number is $2$. Let $H=\{g\in S_n\mid g(n)=n\}$. It is easy to check that $\operatorname{Cay}(G/H,S)$ is a complete graph (if we forget about loops) and hence its chromatic number is $n$.