Extending the vertex coloring of circulant graph to graph on $p$-group

Question

Let $G_1$ be a circulant graph of prime order $p$. This implies that $G_1$ is the Cayley graph on $\mathbb{Z}_p$ with some generating set $S_1$. I am interested in knowing the characterizations of the generating sets $S$ of Cayley graphs $G$ on arbitrary $p$- groups with $S=S_1\cup S_2$, $S_2$ consisting of elements not in $\mathbb{Z}_p$, such that the vertex coloring of the graph $G_1$ can be extended to the vertices of $G$.

Specifically, I ask for what kind of and how many elements can the set $S_2$ have. Suppose I had just one element in $S_2$, then by taking cosets with respect to an element not in $S$ of the colored independent sets of $G_1$, we could easily produce a coloring with the same number of colors for the vertices of $G$. But, this process of taking cosets will not be fruitful if we have more number of elements. So how do we give a coloring extension in such a situation. What could be a possible limitation of the number of elements in $S_2$? Any hints? Thanks beforehand.

Answer 1

$S_2$ can have as many elements as you want and they can be more or less arbitrary. Take any $p$-group $G_2$ with any generating set $S_2$ and consider $G=G_1\times G_2$ with generating set $S_1\times\{1\} \cup \{1\}\times S_2$. Then any edge $(x,y) - (x',y')$ in the Cayley graph is either of the form $(x,y) - (s_1 x, y)$ or $(x,y) - (x,s_2 y)$.

Now choose any surjective group homomorphism $f: G_2 \twoheadrightarrow G_1$ (these always exist because $G_2$ is a $p$-group!) and define a vertex colouring $F: G\to G_1$ by setting $F(x,y) := x\cdot f(y)$. This definition always ensures that $F$ is an extension of the identity colouring $G_1\to G_1$ and that $(x,y)$ and $(s_1x, y)$ have different colours.

And if we can guarantee that $f(s_2)\neq 1$ for all $s_2\in S_2$, then we have also guaranteed that $(x,y)$ and $(x,s_2y)$ have different colours. Now, first note that there must be at least one $s_2\in S_2$ with $f(s_2) \neq 1$. Otherwise, all of $S_2$ would be contained in the proper subgroup $\ker(f)$ and could not generate $G_2$. Now simply replace every element $s\in S_2$ that happens to be in $\ker(f)$ with $s':=ss_2$ and you have a new generating set $S_2'$ with $f(S_2') \subseteq G_1\setminus\{1\}$. The generating set may have shrunk a bit, because you may have constructed elements that were already present in $S_2$, but that just means that one of those two elements was redundant anyway, so if you start with a minimal generating set $S_2$ you will end with another minimal generating set $S'$. Or if you want maximally many elements: Choose $S_2 := G_2\setminus\ker(f)$.

(Sidenote: If you consider the Frattini quotient $G_2 / \Phi(G_2)$, you can recognise that this is really the statement that there is a (minimal) generating set of $\mathbb{F}_p^n$ such that all vectors in it have first component $\neq 0$)