Return to 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 guess 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,kn-1\}$ which we regard as a cyclic group under addition modulo $kn$, and let $$S_{k,n}=\{x\in V_{k,n}:x\lt\frac{kn}2\text{ and }x\text{ is not divisible by }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\}$ 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.)

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

For $k\in\mathbb N$ the random $n$-chromatic countably infinite graph is vertex transitive and contains an isomorphic copy of every $n$-colorable countable graph as an induced subgraph. I guess 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,kn-1\}$ which we regard as a cyclic group under addition modulo $kn$, and let $$S_{k,n}=\{x\in V_{k,n}:x\lt\frac{kn}2\text{ and }x\text{ is not divisible by }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\}$ 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.)

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 guess 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,kn-1\}$ which we regard as a cyclic group under addition modulo $kn$, and let $$S_{k,n}=\{x\in V_{k,n}:x\lt\frac{kn}2\text{ and }x\text{ is not divisible by }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\}$ 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.)

For $k\in\mathbb N$ the random $n$-chromatic countably infinite graph is vertex transitive and contains an isomorphic copy of every $n$-colorable countable graph as an induced subgraph. I guess 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,kn-1\}$ which we regard as a cyclic group under addition modulo $kn$, and let $$S_{k,n}=\{x\in V_{k,n}:x\lt\frac{kn}2\text{ and }x\text{ is not divisible by }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\}$ 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$, 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.)

For $k\in\mathbb N$ the random $n$-chromatic countably infinite graph is vertex transitive and contains an isomorphic copy of every $n$-colorable countable graph as an induced subgraph. I guess 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,kn-1\}$ which we regard as a cyclic group under addition modulo $kn$, and let $$S_{k,n}=\{x\in V_{k,n}:x\lt\frac{kn}2\text{ and }x\text{ is not divisible by }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\}$ 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.)