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


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


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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