Let $n\geq 1$ be an integer. Suppose $m\geq 2n+1$ is an integer. We construct the graph $\mathbb{Z}\_m = (\mathbb{Z}/m\mathbb{Z}, E\_m)$ where $$E\_m=\big\{\{x,y\}:x, y \in \mathbb{Z}/m\mathbb{Z} \text{ and } \exists k\in\{1,\ldots n\}: (x+k = y \text{ or } y+k = x)\big\}.$$


It is easy to see that $\mathbb{Z}\_m$ is a $2n$-regular graph on $m$ vertices.


**Question.** Suppose $c$ is the maximum chromatic number that a $2n$-regular graph on $m$ vertices can have, and let $G=(V,E)$ be a $2n$-regular graph with $|V| = m$ and $\chi(G) = c$. Does this imply that $G\cong \mathbb{Z}\_m$?



$2n$-regular graphs with maximal chromatic number
**Example 1.** Let $n=1$, $m=7$. Then $c=3$, and $G=C\_3+C\_4$ is a $2$-regular graph of order $7$ and chromatic number $3$, but is not isomorphic to $\mathbb Z\_7$.


**Example 2.** Let $n=2$, $m=15$. Then $c=5$, as $G=3K\_5$ is a $4$-regular graph of order $15$ and chromatic number $5$, but $\mathbb Z\_{15}$ has chromatic number $3$.


