Return to Answer

The Cayley graph is bipartite if and only if there exists a homomorphism $\pi\colon G\to\mathbb Z/2\mathbb Z=\{0,1\}$ such that $\pi(S)=\{1\}$.

If such a map exists, then the sets $\pi^{-1}(0)$ and $\pi^{-1}(1)$ give a legal coloring. Conversely, if $\operatorname{Cay}(G,S)$ is bipartite, then $$\pi(g)=d_S(g,e_G)\pmod 2$$ is such a map.

Moreover, this condition can easily be checked from a presentation: is every relation of even length?

The Cayley graph is bipartite if and only if there exists a homomorphism $\pi\colon G\to\mathbb Z/2\mathbb Z=\{0,1\}$ such that $\pi(S) \subseteq \{1\}$.

If such a map exists, then the sets $\pi^{-1}(0)$ and $\pi^{-1}(1)$ give a legal coloring. Conversely, if $\operatorname{Cay}(G,S)$ is bipartite, then $$\pi(g)=d_S(g,e_G)\pmod 2$$ is such a map.

Moreover, this condition can easily be checked from a presentation: is every relation of even length?

The Cayley graph is bipartite if and only if there exists an homomorphism $\pi\colon G\to\mathbb Z/2\mathbb Z=\{0,1\}$ such that $\pi(S)=\{1\}$.

If such a map exists, then the sets $\pi^{-1}(0)$ and $\pi^{-1}(1)$ give a legal coloring. Reciprocally, if $Cay(G,S)$ is bipartite, then $$\pi(g)=d_S(g,e_G)\pmod 2$$ is such a map.

Moreover, this condition can easily be checked from a presentation  : is every relation of even length?

The Cayley graph is bipartite if and only if there exists a homomorphism $\pi\colon G\to\mathbb Z/2\mathbb Z=\{0,1\}$ such that $\pi(S)=\{1\}$.

If such a map exists, then the sets $\pi^{-1}(0)$ and $\pi^{-1}(1)$ give a legal coloring. Conversely, if $\operatorname{Cay}(G,S)$ is bipartite, then $$\pi(g)=d_S(g,e_G)\pmod 2$$ is such a map.

Moreover, this condition can easily be checked from a presentation: is every relation of even length?

The Cayley is bipartite if and only if there exists an homomorphism $\pi\colon G\to\mathbb Z/2\mathbb Z=\{0,1\}$ such that $\pi(S)=\{1\}$.

If such a map exists, then the sets $\pi^{-1}(0)$ and $\pi^{-1}(1)$ give a legal coloring. Reciprocally, if $Cay(G,S)$ is bipartite, then $$\pi(g)=d_S(g,e_G)\pmod 2$$ is such a map.

This can easily be checked from a presentation : is every relation of even length?

The Cayley graph is bipartite if and only if there exists an homomorphism $\pi\colon G\to\mathbb Z/2\mathbb Z=\{0,1\}$ such that $\pi(S)=\{1\}$.

If such a map exists, then the sets $\pi^{-1}(0)$ and $\pi^{-1}(1)$ give a legal coloring. Reciprocally, if $Cay(G,S)$ is bipartite, then $$\pi(g)=d_S(g,e_G)\pmod 2$$ is such a map.

Moreover, this condition can easily be checked from a presentation : is every relation of even length?