Skip to main content
1 of 3

$2n$-regular graphs with maximal chromatic number

Let $G=(V,E)$ be a $2n$-regular graph, where $n\geq 1$ is an integer.

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\neq y \in \mathbb{Z}/m\mathbb{Z} \text{ and } |x-y| \leq n\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$?