Skip to main content
3 of 3
corrected false description of $E_m$

$2n$-regular graphs with maximal chromatic number

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