If $G=(V,E)$ is a simple, undirected graph, is there a vertextransitive graph $G_v$ such that $\chi(G) = \chi(G_v)$ and $G$ is isomorphic to an induced subgraph of $G_v$?
1 Answer
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,nk1\}$ 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,k1\}$ be a proper coloring of $G$. Let $n=2^{p+1}$.
For $i=1,2,\dots,p$, let $x_i=(2^i2)k+c(v_i)\in V_{k,n}$.
Let $T=\{x_ix_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_ix_j$, $1\le j\lt i\le p$, are pairwise distinct.)

$\begingroup$ How to choose $n$ and construct the set $T$ for a given graph? $\endgroup$ Commented Aug 25, 2020 at 9:17

$\begingroup$ Thanks. It seems that $x_{i}$ could equal $(i1)k+c(v_{i})$ and, then $n=p+1$. $\endgroup$ Commented Aug 25, 2020 at 12:33

1$\begingroup$ 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_3x_2=x_2x_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_ix_j$ were distinct. $\endgroup$– bofCommented Aug 25, 2020 at 13:24

1

$\begingroup$ I think your graph is a cayley graph, right? $\endgroup$ Commented Aug 30, 2020 at 22:47