# Connected vertex-transitive graphs of fixed chromatic number and arbitrary size

A simple, undirected graph $$G=(V,E)$$ is said to be vertex-transitive if for all $$v,w\in V$$ there is a graph isomorphism $$\varphi:V\to V$$ such that $$\varphi(v) = w$$.

The cyclic graphs $$C_{2n+1}$$ are vertex-transitive with chromatic number $$3$$.

Given any integers $$k\geq 4$$ and $$n\geq k$$, is there always a connected vertex-transitive graph $$G=(V,E)$$ with $$\chi(G)=k$$ and $$|V|\geq n$$?

• What you call "homogeneous" is usually called "vertex-transitive": see en.wikipedia.org/wiki/Vertex-transitive_graph Commented Oct 24, 2023 at 19:59
• Interesting that the property of being homogeneous does not involve the quantified-over variables v and w, but does involve free variables a and b. Commented Oct 25, 2023 at 6:37
• Thanks @SamHopkins - will correct this. And thanks user38.* -> I hope there are no more free variables enjoying their freedom Commented Oct 25, 2023 at 7:49

Cartesian product of $$K_k$$ with $$C_m$$, where $$km \geq n$$ will do. It's vertex-transitive and has chromatic number $$k$$.
• Or just take the complete $k$-partite graph $K_{m,m,\dots,m}$.