1
$\begingroup$

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

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ What you call "homogeneous" is usually called "vertex-transitive": see en.wikipedia.org/wiki/Vertex-transitive_graph $\endgroup$
    – Sam Hopkins
    Commented Oct 24, 2023 at 19:59
  • 1
    $\begingroup$ 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. $\endgroup$
    – user3840170
    Commented Oct 25, 2023 at 6:37
  • $\begingroup$ Thanks @SamHopkins - will correct this. And thanks user38.* -> I hope there are no more free variables enjoying their freedom $\endgroup$
    – Dominic van der Zypen
    Commented Oct 25, 2023 at 7:49

1 Answer 1

Reset to default
5
$\begingroup$

Cartesian product of $K_k$ with $C_m$, where $km \geq n$ will do. It's vertex-transitive and has chromatic number $k$.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Or just take the complete $k$-partite graph $K_{m,m,\dots,m}$. $\endgroup$
    – bof
    Commented Oct 24, 2023 at 23:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .