On the packing chromatic number of hypercubes

P. D. TORRES; MARIO VALENCIA-PABON

Electronic Notes in Discrete Mathematics

Elsevier

Año: 2013 vol. 44 p. 263 - 268

1571-0653

The packing chromatic number $chi_rho(G)$ of a graph $G$ is the smallest integer $k$ needed to proper color the vertices of $G$ in such a way that the distance in $G$ between any two vertices having color $i$ be at least $i+1$. Goddard et al. found an upper bound for the hypercubes $H_n$. Moreover, they compute $chi_rho(H_n)$ for $n leq 5$ leaving as an open problem the remaining cases. In this paper, we obtain a better upper bound for  $chi_ ho(H_n)$ and we obtain the exact value of  $chi_rho(H_n)$ for $6 leq n leq 8$.