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


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

  • $\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 $(i-1)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_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. $\endgroup$
    – bof
    Commented Aug 25, 2020 at 13:24
  • 1
    $\begingroup$ Yes. You're right. $\endgroup$ Commented Aug 25, 2020 at 19:40
  • $\begingroup$ I think your graph is a cayley graph, right? $\endgroup$
    – vidyarthi
    Commented Aug 30, 2020 at 22:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.