As requested by the OP, here is a simple example of the fact that the chromatic number may go up, and that the Schreier graph is not a subgraph of the Cayley graph.

Let $k>2$ be odd and $n>1$ be even. Let $G = C_{kn}$ (the cyclic groups on $kn$ elements, it is $\cong \mathbb{Z}/kn\mathbb{Z}$).
Let $S = \lbrace -1, 1\rbrace$ be a [symmetric] generating set of this cyclic group.
Then $\mathrm{Cay}(G,S)$ is a cycle of length $kn$ (in particular it contains no odd cycles, since $n>1$).
There is a [normal] subgroup $H$ in $G$ which is isomorphic to $C_n$ (this is the subgroup generated by $k \in \mathbb{Z}$).
It is fairly standard exercise to check that $G/H \cong C_k$.
By normality $\mathrm{Sch}(G/H,S)$ is isomorphic $\mathrm{Cay}(G/H,S)$ which itself is a cycle of length $k$.

The Schreier Graph $\mathrm{Sch}(G/H,S)$, being an odd cycle, has chromatic number 3 and is not isomorphic to any subgraph of $\mathrm{Cay}(G,S)$ (which is an even cycle with chromatic number 2).

Furthermore, by fixing $k$ an letting $n \to \infty$, the ratio $\frac{\# \text{Vertices of } \mathrm{Cay}(G,S)}{\#\text{Vertices of } \mathrm{Sch}(G/H,S)}$ tends to infinity. By fixing $n$ and letting $k \to \infty$, the ratio remains constant, while the cardinalities tend to infinity.

13more comments