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

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.

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

• Thanks, so this shows the arbitrariness of the cardinality of generating set. But, does this mean that the chromatic number of cayley graph on $p$-groups with any generating set is bounded by the chromatic number of the maximal induced circulant subgraph? Jan 1 at 23:31
• @vidyarthi It does not necessarily mean that. For one, using group homomorphisms as colourings is a very special choice. The largest induced circulant subgraph, i.e. the largest cyclic subgroup is often not the image under any group epimorphisms, so that my method won't apply in the general case. It may be worth asking a separate question for that. Jan 4 at 17:09
• @JohannesHahn I don't understand this comment: " largest induced circulant subgraph, i.e. the largest cyclic subgroup". For example, the graph could be a complete graph, which is (isomorphic to) a circulant graph, but the group might not be cyclic... Jan 9 at 3:30
• @vidyarthi That is extremely far from true. Take a $3$-cube as a Cayley graph on an elementary abelian $2$-group, for example. It contains a bunch of $4$-cycles, which are circulant graphs, but there are no elements of order $4$ in the group. Jan 10 at 17:14
• @vidyarthi If you just construct a few random small Cayley graphs, you will immediately see that induced circulant subgraphs typically have nothing to do with cyclic subgroups. Jan 10 at 17:16