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

$\endgroup$
3
  • 2
    $\begingroup$ What you call "homogeneous" is usually called "vertex-transitive": see en.wikipedia.org/wiki/Vertex-transitive_graph $\endgroup$ 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$ 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$ Commented Oct 25, 2023 at 7:49

1 Answer 1

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

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

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.