Skip to main content
1 of 6
bof
  • 13.4k
  • 2
  • 43
  • 66

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.

bof
  • 13.4k
  • 2
  • 43
  • 66