On the Packing Chromatic Number on Hamming Graphs and General Graphs

Abstract

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 the distance between any two vertices having color $i$ be at least $i+1$. We obtain ${\chi }_{\rho }(H_{q,m})$ for $m=3$, where $H_{q,m}$ is the Hamming graph of words of length $m$ and alphabet with $q$ symbols, and tabulate bounds of them for $m\ge 4$ up to 10000 vertices. We also give a polynomial reduction from the problem of finding ${\chi }_{\rho }(G)$ to the Maximum Stable Set problem.

Accepted in Simpósio Brasileiro de Pesquisa Operacional XLVII (SBPO 2015) Web page: http://cdsid.org.br/sbpo2015