Embedding any graph into a vertex-transitive graph of the same chromatic number

If $$G=(V,E)$$ is a simple, undirected graph, is there a vertex-transitive graph $$G_v$$ such that $$\chi(G) = \chi(G_v)$$ and $$G$$ is isomorphic to an induced subgraph of $$G_v$$?

For $$k\in\mathbb N$$ the random $$k$$-chromatic countably infinite graph is vertex transitive and contains an isomorphic copy of every $$k$$-colorable countable graph as an induced subgraph. I suppose this can be generalized somehow to uncountable graphs and infinite chromatic numbers, but I don't think anyone is interested in that. Instead, I'm guessing you are interested in the case where $$G$$ is a finite graph, and you want $$G_v$$ to be finite as well. I believe that can be done.

For $$k,n\in\mathbb N$$ let $$V_{k,n}=\{0,1,\dots,nk-1\}$$ and let $$S_{k,n}=\{t\in V_{k,n}:t\lt\frac{nk}2\text{ and }t\text{ is not a multiple of }k\}.$$ For any set $$T\subseteq S_{k,n}$$ let $$G_{k,n,T}$$ be the graph with vertex set $$V_{k,n}$$ and edges $$\{x,x+t\}$$ (addition modulo $$nk$$) where $$t\in T$$.

Plainly $$G_{k,n,T}$$ is vertex transitive and $$k$$-colorable. Moreover, given any $$k$$-colorable finite graph $$G$$, for sufficiently large $$n$$ we can construct a set $$T\subseteq S_{k,n}$$ so that $$G_{k,n,T}$$ contains an isomorphic copy of $$G$$ as an induced subgraph.

Suppose $$G$$ is a $$k$$-colorable graph of order $$p$$; let $$V(G)=\{v_1,v_2,\dots,v_p\}$$, and let $$c:V(G)\to\{0,1,\dots,k-1\}$$ be a proper coloring of $$G$$. Let $$n=2^{p+1}$$.

For $$i=1,2,\dots,p$$, let $$x_i=(2^i-2)k+c(v_i)\in V_{k,n}$$.

Let $$T=\{x_i-x_j:i\gt j,\ v_iv_j\in E(G)\}$$.

Then $$T\subseteq S_{k,n}$$, and the mapping $$v_i\mapsto x_i$$ is an isomorphism between $$G$$ and an induced subgraph of $$G_{k,n,T}$$. (Note that the $$\binom p2$$ differences $$x_i-x_j$$, $$1\le j\lt i\le p$$, are pairwise distinct.)

• How to choose $n$ and construct the set $T$ for a given graph? Commented Aug 25, 2020 at 9:17
• Thanks. It seems that $x_{i}$ could equal $(i-1)k+c(v_{i})$ and, then $n=p+1$. Commented Aug 25, 2020 at 12:33
• I don't think so. Suppose $c(v_1)=0$, $c(v_2)=1$, $c(v_3)=2$; then you would have $x_1=0$, $x_2=k+1$, $x_3=2k+2$, and so $x_3-x_2=x_2-x_1=k+1$, which is a problem if $v_1v_2\in E(G)$ while $v_2v_3\notin E(G)$. I wanted to make sure that all the differences $x_i-x_j$ were distinct.
– bof
Commented Aug 25, 2020 at 13:24
• Yes. You're right. Commented Aug 25, 2020 at 19:40
• I think your graph is a cayley graph, right? Commented Aug 30, 2020 at 22:47