The packing chromatic number of hypercubes ?
The packing chromatic number ??(G) ? ? ( G ) of a graph G G is the smallest integer k k needed to proper color the vertices of G G in such a way that the distance in G G between any two vertices having color i i be at least i+1 i + 1 . Goddard etal. (2008) found an upper bound for the packing chromatic number of hypercubes Qn Q n . Moreover, they compute ??(Qn) ? ? ( Q n ) for n?5 n ? 5 leaving as an open problem the remaining cases. In this paper, we obtain a better upper bound for ??(Qn) ? ? ( Q n ) and we improve the lower bounds for ??(Qn) ? ? ( Q n ) for 6?n?11 6 ? n ? 11 . In particular we compute the exact value of ??(Qn) ? ? ( Q n ) for 6?n?8 6 ? n ? 8 .
packing chromatic number upper bound hypercube graphs