On the packing chromatic number of hypercubes
Résumé
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. \cite{Goddard08} 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 compute the exact value of $\chi_\rho(Q_n)$ for $6 \leq n \leq 8$.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...