Packing coloring of hypercubes with extended Hamming codes

P Gregor, J Kranjc, B Lužar, K Štorgel - Discrete Applied Mathematics, 2024 - Elsevier
P Gregor, J Kranjc, B Lužar, K Štorgel
Discrete Applied Mathematics, 2024Elsevier
A packing k-coloring of a graph G is a mapping assigning a positive integer (a color) from
the set 1,…, k to every vertex of G such that every two distinct vertices of color c are at
distance at least c+ 1. The minimum value k such that G admits a packing k-coloring is called
the packing chromatic number of G. In this paper, we continue the study of the packing
chromatic number of hypercubes and we improve the upper bounds reported by Torres and
Valencia-Pabon (2015) by presenting recursive constructions of subsets of distant vertices …
A packing k-coloring of a graph G is a mapping assigning a positive integer (a color) from the set 1,…, k to every vertex of G such that every two distinct vertices of color c are at distance at least c+ 1. The minimum value k such that G admits a packing k-coloring is called the packing chromatic number of G. In this paper, we continue the study of the packing chromatic number of hypercubes and we improve the upper bounds reported by Torres and Valencia-Pabon (2015) by presenting recursive constructions of subsets of distant vertices making use of the properties of the extended Hamming codes. We also answer in negative a question on the packing chromatic number of Cartesian products raised by Brešar et al.(2007).
Elsevier