Coloring of the dth power of the face-centered cubic grid

Nicolas Gastineau (1) , Olivier Togni (1)

1 LIB - Laboratoire d'Informatique de Bourgogne [Dijon]

The face-centered cubic grid is a three dimensional 12-regular infinite grid. This graph represents an optimal way to pack spheres in the three-dimensional space. In this grid, the vertices represent the spheres and the edges represent the contact between spheres. We give lower and upper bounds on the chromatic number of the d th power of the face-centered cubic grid. In particular, in the case d = 2 we prove that the chromatic number of this grid is 13. We also determine sharper bounds for d = 3 and for subgraphs of of the face-centered cubic grid.

Domaines: Mathématique discrète [cs.DM]

Nicolas Gastineau, Olivier Togni. Coloring of the dth power of the face-centered cubic grid. Discussiones Mathematicae Graph Theory, 2021, 41, pp.1001-1020. ⟨10.7151/dmgt.2257⟩. ⟨hal-01819684⟩