The packing chromatic number of hypercubes

PABLO TORRES; MARIO VALENCIA-PABON

DISCRETE APPLIED MATHEMATICS

ELSEVIER SCIENCE BV

Lugar: Amsterdam; Año: 2015 vol. 190 p. 127 - 140

0166-218X

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 packing chromatic number of hypercubes $Q_n$. Moreover, they compute $chi_ rho(Q_n)$ for $n leq 5$ leaving as an open problem the remaining cases. In this paper, we obtain a better upper bound for  $chi_ rho(Q_n)$ and we improve the lower bounds for $chi_rho(Q_n)$ for $6 leq n leq 11$. In particular we compute the exact value of  $chi_ rho(Q_n)$ for $6 leq n leq 8$.