Geodesic
Coloring of the dth Power of the Face-Centered Cubic Grid
Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 4, pp. 1001-1020 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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. We give lower and upper bounds on the chromatic number of the dth 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 the face-centered cubic grid.
Keywords: face-centered cubic grid, distance coloring, dth power of graph 
@article{DMGT_2021_41_4_a8,
     author = {Gastineau, Nicolas and Togni, Olivier},
     title = {Coloring of the d\protect\textsuperscript{th} {Power} of the {Face-Centered} {Cubic} {Grid}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1001--1020},
     year = {2021},
     volume = {41},
     number = {4},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2021_41_4_a8/}
}
TY  - JOUR
AU  - Gastineau, Nicolas
AU  - Togni, Olivier
TI  - Coloring of the dth Power of the Face-Centered Cubic Grid
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2021
SP  - 1001
EP  - 1020
VL  - 41
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DMGT_2021_41_4_a8/
LA  - en
ID  - DMGT_2021_41_4_a8
ER  - 
%0 Journal Article
%A Gastineau, Nicolas
%A Togni, Olivier
%T Coloring of the dth Power of the Face-Centered Cubic Grid
%J Discussiones Mathematicae. Graph Theory
%D 2021
%P 1001-1020
%V 41
%N 4
%U http://geodesic.mathdoc.fr/item/DMGT_2021_41_4_a8/
%G en
%F DMGT_2021_41_4_a8
Gastineau, Nicolas; Togni, Olivier. Coloring of the dth Power of the Face-Centered Cubic Grid. Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 4, pp. 1001-1020. http://geodesic.mathdoc.fr/item/DMGT_2021_41_4_a8/

[1] S. Bjørnholm, Clusters, condensed matter in embryonic form, Contemp. Phys. 31 (1990) 309–324. https://doi.org/10.1080/00107519008213781

[2] J. Bourgeois and S. Copen Goldstein, Distributed intelligent MEMS: progresses and perspectives, IEEE Syst. J. 9 (2015) 1057–1068. https://doi.org/10.1109/JSYST.2013.2281124

[3] J.J. Daymude, R. Gmyr, A.W. Richa, C. Scheideler and T. Strothmann, Improved leader election for self-organizing programmable matter, in: Algorithms for Sensor Systems, ALGOSENSORS 2017, Lecture Notes in Comput. Sci. 10718 (2017) 127–140. https://doi.org/10.1007/978-3-319-72751-6_-10

[4] G. Fertin, E. Godard and A. Raspaud, Acyclic and k-distance coloring of the grid, Inform. Process. Lett. 87 (2003) 51–58. https://doi.org/10.1016/S0020-0190(03)00232-1

[5] P. Jacko and S. Jendrol’, Distance coloring of the hexagonal lattice, Discuss. Math. Graph Theory 25 (2005) 151–166. https://doi.org/10.7151/dmgt.1269

[6] F. Kramer and H. Kramer, A survey on the distance-colouring of graphs, Discrete Math. 308 (2008) 422–426. https://doi.org/10.1016/j.disc.2006.11.059

[7] B. Piranda and J. Bourgeois, Geometrical study of a quasi-spherical module for building programmable matter, in: Distributed Autonomous Robotic Systems, Springer Proc. Adv. Robot. 6 (2018) 347–400. https://doi.org/10.1007/978-3-319-73008-0_27

[8] A. Ševčiková, Distant Chromatic Number of the Planar Graphs (2001), manuscript.

[9] P. Šparl, R. Witkowski and J. Žerovnik, Multicoloring of cannonball graphs, Ars Math. Contemp. 10 (2016) 31–44. https://doi.org/10.26493/1855-3974.528.751