Chromatic number of Voronoi diagrams of lattices

Let $L$ be a Euclidean lattice. Define a graph whose vertex set is $L$ and where two points $x,y\in L$ are declared to be adjacent whenever the cells of $x$ and $y$ in the Voronoi diagram of $L$ have a facet in common, or equivalently¹, when $z := x-y$ and $-z$ are the only shortest vectors in the coset $z + 2L$ (such vectors $z$ are called "relevant"). Let $\chi(L)$ be the chromatic number of this graph (i.e., the minimal number of colors required to color the Voronoi diagram of $L$ such that two cells sharing a facet never have the same color).

Main question: Does this quantity $\chi(L)$ appear in the literature? Does it have a name? What are the standard facts about it?

Trivial observation: $\chi(L) \leq 2^d$ where $d$ is the dimension of $L$. (Proof: color $L$ by mapping $x\in L$ to its coset in $L/2L$.)

More specific question: What is the value of $\chi(L)$ for some standard lattices like the root lattices, their duals, and the Leech lattice?

Note: If $L$ is a root lattice, then the relevant vectors are precisely the roots. (In fact, this characterizes root lattices: Rajan & Shande, "A Characterization of Root Lattices", Discrete Math. 161 (1996), 309–314.)

Example observation: $\chi(A_n) \leq n+1$. (Proof: color $(x_0,\ldots,x_n)\in\mathbb{Z}^{n+1}$ such that $\sum_i x_i = 0$ by $\sum_i i x_i$ mod $n+1$.) This inequality is sharp as Fedor Petrov points out in a comment below. Even more trivially, $\chi(\mathbb{Z}^n) = 2$ (using a checkerboard coloring).

1. Conway & Sloane, Sphere Packings, Lattices and Groups (Springer 3rd ed., 1999), theorem 10 of chapter 21.
• $\chi(A_n)=n+1$, since the elements $0,x_0-x_i,1\leqslant i\leqslant n$, should have different colors. Commented Apr 11, 2017 at 14:47

1 Answer

It's been a bit long in the making, but Mathieu Dutour Sikirić, Philippe Moustrou, Frank Vallentin and I just uploaded to the arXiv a paper on “Coloring the Voronoi tessellation of lattices” which answers some aspects of the above question. In particular, we computed the following chromatic numbers:

• $$n+1$$ for the root lattice $$A_n$$ and its dual $$A_n^*$$,

• the chromatic number of the half-cube graph for the root lattice $$D_n$$, and $$4$$ for its dual $$D_n^*$$,

• $$9,14,16$$ for the root lattices $$E_6,E_7,E_8$$, and $$16$$ for their duals $$E_6^*$$ and $$E_7^*$$,

• and $$4096$$ for the Leech lattice.

We also show that the greatest chromatic number of an $$n$$-dimensional lattice grows exponentially with $$n$$.