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

Question

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

Answer 1

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